Trees · routine

Height of a tree

A TreeNode has a value, a left and a right child (either may be None). Write height(root): the number of nodes on the longest path from the root down to a leaf. An empty tree has height 0.

right answers
arguments left as they should be

Already written for you — you can use these

1class TreeNode:
2    def __init__(self, value, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6 
7def bst(values):
8    """A balanced binary search tree holding the sorted values."""
9    if not values:
10        return None
11    mid = len(values) // 2
12    return TreeNode(values[mid], bst(values[:mid]), bst(values[mid + 1:]))

def height(root):
    if root is None:
        return 0
    return 1 + height(root.left)

Run adds print(height(bst([1, 2, 3, 4, 5, 6, 7]))) after your code, to try it.

Stuck on the idea rather than the code? The Trees lesson walks through it.