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. 

  18.     def getHeight(self,root):

  19.         if root:

  20.             leftDepth = self.getHeight(root.left)

  21.             rightDepth = self.getHeight(root.right)

  22.             

  23.             if leftDepth > rightDepth:

  24.                 return leftDepth + 1

  25.             else: 

  26.                 return rightDepth + 1

  27.         else:

  28.             return -1

  29. 

  30. T=int(input())

  31. myTree=Solution()

  32. root=None

  33. for i in range(T):

  34.     data=int(input())

  35.     root=myTree.insert(root,data)

  36. height=myTree.getHeight(root)

  37. print(height)
download android app