Tree patterns

Most tree questions are solved by one of two walks. (The Python course's binary-trees lesson builds the tree used here.)

Depth-first: ask the children

Many answers about a tree come from the answers about its two subtrees. Write the function as if it already works for the children, then combine:

def depth(node):
    if node is None:          # the base case: an empty tree
        return 0
    return 1 + max(depth(node.left), depth(node.right))

The same shape gives the number of nodes, the sum of the values, whether two trees are equal, and whether a tree is balanced. The only questions are: what is the answer for an empty tree, and how do the children's answers combine?

Breadth-first: level by level

To visit a tree level by level (the level-order traversal, the rightmost node of each level, the minimum depth), use a queue. Taking exactly len(queue) nodes in each round processes one whole level:

from collections import deque

class Node:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def levels(root):
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):        # exactly the nodes of this level
            node = queue.popleft()
            level.append(node.value)
            for child in (node.left, node.right):
                if child:
                    queue.append(child)
        result.append(level)
    return result

tree = Node(8, Node(3, Node(1), Node(6)), Node(10, None, Node(14)))
print(levels(tree))

Validating a binary search tree

In a binary search tree (BST), every value in the left subtree is smaller than the node, and every value in the right subtree is bigger. A classic wrong answer only checks each node against its two children. The value must fit between bounds inherited from all its ancestors:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def is_bst(node, low=float("-inf"), high=float("inf")):
    if node is None:
        return True
    if not low < node.value < high:
        return False
    return is_bst(node.left, low, node.value) and is_bst(node.right, node.value, high)

good = Node(5, Node(3, Node(2), Node(4)), Node(8))
bad = Node(5, Node(3, Node(2), Node(6)), Node(8))     # 6 is left of 5
print(is_bst(good), is_bst(bad))

In the second tree, 6 is a correct right child of 3 (it is bigger than 3), so comparing each node with its children finds nothing wrong. But 6 is in the left subtree of 5, so it must be smaller than 5. Only the bounds catch it.

Another way: an in-order walk (left, node, right) of a BST visits the values in increasing order, so check that each value is bigger than the previous one.

The lowest common ancestor

The lowest common ancestor (LCA) of two nodes is the deepest node that has both below it. In a BST it is easy: start at the root; if both values are smaller, go left; if both are bigger, go right; otherwise this node splits them, and it is the LCA. In a general binary tree, recurse: a node is the LCA if one target is found in each subtree (or the node is one of the targets and the other is below it).

Mark lesson complete