Tree Size and Height
Recursive measurements.
Trees and recursion are made for each other. A tree is a node, with two smaller trees hanging below it. So most tree questions have the same answer. Ask the left subtree, ask the right subtree, and combine.

- A tree is made of smaller trees
- Ask left, ask right
- Combine the answers
Size, height and total
The size of a tree is one, for this node, plus the sizes of both subtrees. Its height is one, plus the taller of the two subtrees. And the total is this value, plus both totals. An empty tree is the base case for all three, and gives zero. Run it.
from tree import sample
def size(n):
return 1 + size(n.left) + size(n.right) if n else 0
def height(n):
return 1 + max(height(n.left), height(n.right)) if n else 0
def total(n):
return n.value + total(n.left) + total(n.right) if n else 0
root = sample()
print("size:", size(root), "height:", height(root), "total:", total(root))size: 9 height: 4 total: 66
Also uses tree.py
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
def sample():
return TreeNode(8,
TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
TreeNode(10, None, TreeNode(14, TreeNode(13))))
PICTURE = ' 8\n / \\\n 3 10\n / \\ \\\n 1 6 14\n / \\ /\n 4 7 13'The tree recipe
Almost every tree function has this shape. If the node is empty, return the base answer. Otherwise, call the function on the left child, then on the right child, and combine the two answers with this node. Each node is visited once, so it's O of N.
| key | value |
|---|---|
| Empty node | base answer |
| Left | recurse |
| Right | recurse |
| Combine | with this node |
Summary
Size, height, and total all follow one recipe. Ask both subtrees, then combine. Next, a special tree that keeps values in order. The binary search tree.
Key takeaways- size = 1 + left + right
- height = 1 + max(...)
- Empty tree = 0