Hackerrank Tree: Height of a Binary Tree (Python3)

Challenge

Solution

I simply recur down the tree, and take the max value of the heights and add one to the max value. I also return a height of -1 in the base case, because if we make the height of the non-existent child to be -1, the parent which is the leaf node, will then have the correct height of 1 + -1 = 0 according to the else case.

def height(root):
    '''
    Looked up online to see whether my first intuition
    of doing simple recursion and adding was good one.
    '''
    '''
    TOC: <20 m
    Complexity: TBD
    '''
    if not root:
        return -1
    else:
        return 1 + max(height(root.left), height(root.right))

tree = BinarySearchTree()
arr = [3, 5, 2, 1, 4, 6, 7]
for i in range(len(arr)):
    tree.create(arr[i])


print(height(tree.root))