Trees

Every node has children, and recursion walks them. · 10 minutes

A binary tree is nodes with up to two children, left and right. Most tree code has the same shape: handle the empty tree, then solve the problem for each child and combine the answers.

In a binary search tree, everything on a node's left is smaller than it and everything on its right is bigger — the tree version of a sorted list.

Predict first

What does size(root) compute?

1def size(node):
2    if node is None:
3        return 0
4    return 1 + size(node.left) + size(node.right)