Python Day 22: Binary Search Trees




The height of a binary search tree is the number of edges between the tree's root and its furthest leaf. You are given a pointer, root, pointing to the root of a binary search tree. Complete the getHeight function provided in your editor so that it returns the height of the binary search tree.



  1. class Node:
  2. def __init__(self,data):
  3. self.right=self.left=None
  4. self.data = data
  5. class Solution:
  6. def insert(self,root,data):
  7. if root==None:
  8. return Node(data)
  9. else:
  10. if data<=root.data:
  11. cur=self.insert(root.left,data)
  12. root.left=cur
  13. else:
  14. cur=self.insert(root.right,data)
  15. root.right=cur
  16. return root
  17. def getHeight(self,root):
  18. if root:
  19. leftDepth = self.getHeight(root.left)
  20. rightDepth = self.getHeight(root.right)
  21. if leftDepth > rightDepth:
  22. return leftDepth + 1
  23. else:
  24. return rightDepth + 1
  25. else:
  26. return -1
  27. T=int(input())
  28. myTree=Solution()
  29. root=None
  30. for i in range(T):
  31. data=int(input())
  32. root=myTree.insert(root,data)
  33. height=myTree.getHeight(root)
  34. print(height)




codesadda.com

Codesadda.com is your home of programming solutions, tutorials, video tutorials and much more. Sign Up for our weekly newsletter to get update about new content.

Like us on Facebook | Connect with us on LinkedIn | Subscribe our Channel on Youtube