Card 05/ 08
Tree Functions Combine Two Recursive Results
Ask each subtree for its answer, then combine the two with the node's own value.
Most functions on a binary tree are written the same way: ask the left subtree for its answer, ask the right subtree for its answer, and combine the two with the node itself. This card covers that pattern, the base case that answers for an empty tree, and four functions built from it: height, size, sum and largest value.
The pattern follows the recursive definition of a binary tree, which is either empty or a node with a left subtree and a right subtree. A function written to that definition has two cases. The base case is the empty tree, which has no node to look at, so its answer is fixed. The recursive case calls the function on each subtree, trusts each call to return the right answer for its smaller tree, and combines the two answers with what the node itself contributes. Only the base case's answer and the combine step change from one function to the next.
| Function | The empty tree returns | A node returns |
|---|---|---|
| Height, in edges | -1 | 1 + the larger of the two subtrees' heights |
| Size, the number of nodes | 0 | 1 + the left size + the right size |
| Sum of the values | 0 | The node's value + the left sum + the right sum |
| Largest value | Negative infinity, below every value | The largest of the node's value and the two subtrees' answers |
The listing writes each row as a function, with the combine steps highlighted. It runs them on a tree with the same shape as the one used throughout this topic, given different values so that the sum and the largest value have something to show: 10 at the root, with children 4 and 5; 4 with children 8 and 1; 5 with only a right child, 9; and 9 with only a left child, 3.
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def height(node):
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
def size(node):
if node is None:
return 0
return 1 + size(node.left) + size(node.right)
def total(node):
if node is None:
return 0
return node.value + total(node.left) + total(node.right)
def largest(node):
if node is None:
return float("-inf")
return max(node.value, largest(node.left), largest(node.right))
root = Node(10, Node(4, Node(8), Node(1)), Node(5, None, Node(9, Node(3))))
print("height", height(root))
print("size", size(root))
print("total", total(root))
print("largest", largest(root))height 3
size 7
total 40
largest 10The answers are built from the bottom up. A leaf gets -1 from each of its empty subtrees and returns 1 + -1, which is 0. Its parent then gets two heights and adds 1 to the larger. Each note gives the height that node's call returned, as an instrumented copy of height printed it.
10, left 1, right 2: returns 3
4, left 0, right 0: returns 1
8, returns 0
1, returns 0
5, left -1, right 1: returns 2
null, returns -1
9, left 0, right -1: returns 1
3, returns 0
A node can combine only after both its subtrees have returned, so the combining happens in post-order. Each function calls itself once per node and once per empty link, so it runs in O(n) time on n nodes, and the call stack holds one frame for each node on the path being explored, which in a tree shaped like a long chain is nearly all of them.
← → move through sections and cards