Python Binary Search Tree
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.
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.
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)
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!