Python Binary Search Tree | David Capella
View on GitHub

David Capella

Data Engineer

Python Binary Search Tree

HackerRank

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.

Process

white-board-bst

Starting at the top of the tree we need to keep count. Meaning that will be 0. Going down, there will be a left node and a right node meaning we will need the max of the two Nodes.

If the left node is not none then we add 1 and continue down. Same for the right node. Continuing down means looping or in this case recursion because that will work best. Once we get to the last node (or leaf), we return the max of the two nodes which should be 0.

Each time we go back up it will be adding 1 to whatever was return. So one node above the last will be 1 + 0, after that it will be 1 + 1, 1 + 2, etc.

Code

def getHeight(self,root):
  # To keep count declare at 0 for top of node
  left_node = 0
  right_node = 0
  
  # Check if we keep going down or not
  if root.left is not None:
    # If we do go down, to keep count, we add 1 to however far we go.
    left_node = 1 + self.getHeight(root.left)
  
  # Repeat for right side
  if root.right is not None:
    right_node = 1 + self.getHeight(root.right)

  # If we are at the last leaf, then only return the max of the two
  return max(left_node, right_node)

Conclusion

This was probably one of the more hard ones that I have done. It has been awhile since I worked with something like this. Very exciting/fun to work it out on the board and even get stuck along the way. Definitely took longer than I would have liked but very much worth it. Looking forward to the next one!