Recursion on Trees: Heights, Paths and Return Values
What each call hands back
Every recursive function on a tree has two channels. Arguments carry facts down, from a node to its children: the largest value seen so far, the path walked so far. Return values carry facts up, from the children to their parent: a height, a count, whether a subtree is balanced. Choosing which way each fact travels is most of the work, and five problems in this lesson show the choice:
| Problem | Down, as arguments | Up, as return values | The answer |
|---|---|---|---|
| Maximum Depth of Binary Tree | nothing | the depth below | the root's return |
| Balanced Binary Tree | nothing | the height, or −1 if not balanced | the root's return |
| Diameter of Binary Tree | nothing | the height | the best bend, kept beside the calls |
| Count Good Nodes in Binary Tree | the largest value above | a count | the root's count |
| Path Sum III | the running sum | a count | the root's count |
The third row is the interesting one. The answer, the longest path, isn't what a parent needs from its child, so the function returns one thing and keeps the answer somewhere else. Most of the hard tree problems are that shape.
Return what the parent needs
Balanced Binary Tree asks whether every node's two subtrees differ in height by at most one. The first answer most people write checks the heights at the root, then calls itself on both children, and computes the same heights again and again on the way down. A parent needs two facts from each child, its height and whether it's balanced, so return both at once. One number can carry both: the height when the subtree is balanced, and −1, which no height can be, when it isn't:
// The height of a balanced tree, or -1 as soon as any subtree isn't balanced.
int heightIfBalanced(TreeNode* node) {
if (node == nullptr) return 0;
int left = heightIfBalanced(node->left);
if (left == -1) return -1; // an unbalanced subtree: stop
int right = heightIfBalanced(node->right);
if (right == -1 || abs(left - right) > 1) return -1;
return 1 + max(left, right);
}
bool isBalanced(TreeNode* root) {
return heightIfBalanced(root) != -1;
}
def height_if_balanced(node):
"""The height of a balanced tree, or -1 as soon as any subtree isn't balanced."""
if node is None:
return 0
left = height_if_balanced(node.left)
if left == -1: # an unbalanced subtree: stop
return -1
right = height_if_balanced(node.right)
if right == -1 or abs(left - right) > 1:
return -1
return 1 + max(left, right)
def is_balanced(root):
return height_if_balanced(root) != -1
// The height of a balanced tree, or -1 as soon as any subtree isn't balanced.
static int heightIfBalanced(TreeNode node) {
if (node == null) return 0;
int left = heightIfBalanced(node.left);
if (left == -1) return -1; // an unbalanced subtree: stop
int right = heightIfBalanced(node.right);
if (right == -1 || Math.abs(left - right) > 1) return -1;
return 1 + Math.max(left, right);
}
static boolean isBalanced(TreeNode root) {
return heightIfBalanced(root) != -1;
}
// The height of a balanced tree, or -1 as soon as any subtree isn't balanced.
function heightIfBalanced(node) {
if (node === null) return 0;
const left = heightIfBalanced(node.left);
if (left === -1) return -1; // an unbalanced subtree: stop
const right = heightIfBalanced(node.right);
if (right === -1 || Math.abs(left - right) > 1) return -1;
return 1 + Math.max(left, right);
}
function isBalanced(root) {
return heightIfBalanced(root) !== -1;
}
Each printed true false true false on the problem's examples, [3, 9, 20, null, null, 15, 7], [1, 2, 2, 3, 3, null, null, 4, 4], [], and on [1, 2, 2, 3, null, null, 3, 4, null, null, 4]. That last one is the trap: the root's two subtrees both have height 3, so the root alone looks fine, but the 2s below it are not. Each node is visited once, O(n), and the −1 stops the walk at the first subtree that fails.
An answer kept beside the calls
Diameter of Binary Tree wants the longest path between any two nodes, counted in edges. That path goes up from one node, bends at the highest node on it, and comes down to the other. Bending at a node, the longest path it can make is the longest way down its left side plus the longest way down its right side: its children's heights, added.
The direct way computes that for every node by measuring both heights from scratch:
| Nodes | Levels | Heights measured at every node | Heights returned once |
|---|---|---|---|
| 1,000 | 501 | 95.8 ms | 0.69 ms |
| 2,000 | 1,001 | 387.4 ms | 1.28 ms |
| 4,000 | 2,001 | 1,571.8 ms | 2.65 ms |
That's on our judge in Python, on trees with a long right-hand chain and a leaf off every node. Each height costs a walk of the subtree, so a deep tree pays O(n²): twice the nodes, four times the time. Every height is already on its way back up in the recursion, though. Let each call return its height, and use the two heights it just got back to measure the bend at that node. The parent needs only the height, so the best bend is kept in a variable outside the calls:
// Each call returns its height; the longest path bending at a node is kept in best.
int heightThrough(TreeNode* node, int& best) {
if (node == nullptr) return 0;
int left = heightThrough(node->left, best);
int right = heightThrough(node->right, best);
best = max(best, left + right); // the longest path that bends here, in edges
return 1 + max(left, right); // the parent can use one side only
}
int diameterOfBinaryTree(TreeNode* root) {
int best = 0;
heightThrough(root, best);
return best;
}
def diameter(root):
"""The longest path between two nodes, in edges."""
best = 0
def height_through(node):
nonlocal best
if node is None:
return 0
left, right = height_through(node.left), height_through(node.right)
best = max(best, left + right) # the longest path that bends here, in edges
return 1 + max(left, right) # the parent can use one side only
height_through(root)
return best
// Each call returns its height; the longest path bending at a node is kept in best[0].
static int heightThrough(TreeNode node, int[] best) {
if (node == null) return 0;
int left = heightThrough(node.left, best);
int right = heightThrough(node.right, best);
best[0] = Math.max(best[0], left + right); // the longest path that bends here, in edges
return 1 + Math.max(left, right); // the parent can use one side only
}
static int diameterOfBinaryTree(TreeNode root) {
int[] best = {0};
heightThrough(root, best);
return best[0];
}
// The longest path between two nodes, in edges.
function diameterOfBinaryTree(root) {
let best = 0;
function heightThrough(node) {
if (node === null) return 0;
const left = heightThrough(node.left);
const right = heightThrough(node.right);
best = Math.max(best, left + right); // the longest path that bends here, in edges
return 1 + Math.max(left, right); // the parent can use one side only
}
heightThrough(root);
return best;
}
Each printed 3 1 5: the problem's examples, [1, 2, 3, 4, 5] and [1, 2], and [1, 2, null, 3, 4, 5, null, null, 6, 7], whose longest path bends below the root. One visit per node, O(n). Watch the bend move:
The diameter, bend by bend — Indigo is the node answering, violet the nodes done, with the height each returned; green is the node where the best path so far bends.
Binary Tree Maximum Path Sum is the same shape with values instead of lengths. A path may bend at one node, so the best path bending at a node is its value plus the best way down on each side. But the parent can extend only a path that goes straight down, so a node hands up its value plus the better of its two sides. And a side whose best is negative is better left out, so it counts as 0:
// gain(node): the best sum of a path going down from node, which the parent can extend.
int gain(TreeNode* node, int& best) {
if (node == nullptr) return 0;
int left = max(gain(node->left, best), 0); // a side that loses is left out
int right = max(gain(node->right, best), 0);
best = max(best, node->val + left + right); // the best path that bends here
return node->val + max(left, right); // going up, a path takes one side
}
int maxPathSum(TreeNode* root) {
int best = root->val; // not 0: every value may be negative
gain(root, best);
return best;
}
def max_path_sum(root):
best = root.val # not 0: every value may be negative
def gain(node):
"""The best sum of a path going down from node, which the parent can extend."""
nonlocal best
if node is None:
return 0
left = max(gain(node.left), 0) # a side that loses is left out
right = max(gain(node.right), 0)
best = max(best, node.val + left + right) # the best path that bends here
return node.val + max(left, right) # going up, a path takes one side
gain(root)
return best
// gain(node): the best sum of a path going down from node, which the parent can extend.
static int gain(TreeNode node, int[] best) {
if (node == null) return 0;
int left = Math.max(gain(node.left, best), 0); // a side that loses is left out
int right = Math.max(gain(node.right, best), 0);
best[0] = Math.max(best[0], node.val + left + right); // the best path that bends here
return node.val + Math.max(left, right); // going up, a path takes one side
}
static int maxPathSum(TreeNode root) {
int[] best = {root.val}; // not 0: every value may be negative
gain(root, best);
return best[0];
}
// The best path between any two nodes; a path may bend once.
function maxPathSum(root) {
let best = root.val; // not 0: every value may be negative
function gain(node) { // the best path going down from node
if (node === null) return 0;
const left = Math.max(gain(node.left), 0); // a side that loses is left out
const right = Math.max(gain(node.right), 0);
best = Math.max(best, node.val + left + right); // the best path that bends here
return node.val + Math.max(left, right); // going up, a path takes one side
}
gain(root);
return best;
}
Each printed 6 42 -3 2 on [1, 2, 3], [-10, 9, 20, null, null, 15, 7], [-3] and [2, -1]. The best starts at the root's value, not at 0: in [-3] every path is negative, and the answer is −3.
Now you fill in the returns
Below, you are the recursion. For each node, from the leaves up, pick what it returns to its parent and what the best so far becomes. The tree shows each answer as it's given. Pick wrongly and the arithmetic explains why. Switch between the diameter and the maximum path sum: the same shape, two different returns.
State going down
Some answers depend on the path from the root, and the path is known only on the way down, so it travels as an argument.
Good nodes. Count Good Nodes in Binary Tree counts nodes with nothing bigger above them. Pass the largest value on the path so far:
def good_nodes(root):
def count(node, highest):
if node is None:
return 0
good = 1 if node.val >= highest else 0 # nothing above it on the way down is bigger
highest = max(highest, node.val)
return good + count(node.left, highest) + count(node.right, highest)
return count(root, root.val)
It returned 4, 3, 1 on the problem's three examples.
Root-to-leaf paths. Binary Tree Paths passes the path itself, and each child gets its own copy, so one branch's nodes never end up in another branch's path:
def binary_tree_paths(root):
paths = []
def walk(node, path):
path = path + [str(node.val)] # a new list: each branch gets its own copy
if node.left is None and node.right is None:
paths.append("->".join(path))
for child in (node.left, node.right):
if child:
walk(child, path)
walk(root, [])
return paths
On [1, 2, 3, null, 5] it returned ['1->2->5', '1->3'].
Paths with a given sum. Path Sum III counts downward paths, starting anywhere and ending anywhere below, whose values add up to a target. Walking down from every node and adding as you go is correct, and it's O(n · h). The fix is the prefix-sum idea from Introduction to Prefix Sums, run on the path from the root: if the running sum is total at a node, a path ending there sums to the target when an earlier running sum on the same path was total - target. Keep a count of the running sums on the current path, and take a node's sum out of it on the way back up:
from collections import defaultdict
def path_sum(root, target):
"""Downward paths that sum to target: a prefix equal to total - target, on the way down, starts one."""
seen = defaultdict(int)
seen[0] = 1 # the empty prefix, for paths that start at the root
def walk(node, total):
if node is None:
return 0
total += node.val
count = seen[total - target] # paths that end here
seen[total] += 1
count += walk(node.left, total) + walk(node.right, total)
seen[total] -= 1 # leaving this node: its prefix is off the path
return count
return walk(root, 0)
It returned 3 and 3 on the problem's two examples. Step through the first:
Path Sum III with running sums — Indigo is the node reached, amber the path above it, green the nodes of a path that sums to 8; violet nodes are finished. The row holds the running sums on the current path.
Against walking down from every node, on the same deep trees as the diameter:
| Nodes | A walk down from every node | Running sums |
|---|---|---|
| 1,000 | 89.5 ms | 0.72 ms |
| 2,000 | 359.8 ms | 1.29 ms |
| 4,000 | 1,456.8 ms | 2.64 ms |
Both found the same 327,183 paths on the largest tree.
Comparing two trees
A recursion can walk two trees at once. Same Tree compares the roots, then the two left subtrees, then the two right ones. Symmetric Tree asks whether a tree is its own mirror image, which means its left subtree mirrors its right: compare the outside pair, left's left with right's right, and the inside pair, left's right with right's left. Subtree of Another Tree runs Same Tree at every node:
def same_tree(p, q):
if p is None or q is None:
return p is q # both empty, or one missing: a mismatch
return p.val == q.val and same_tree(p.left, q.left) and same_tree(p.right, q.right)
def is_symmetric(root):
def mirror(a, b):
if a is None or b is None:
return a is b
return a.val == b.val and mirror(a.left, b.right) and mirror(a.right, b.left)
return root is None or mirror(root.left, root.right)
def is_subtree(root, sub):
if root is None:
return False
return same_tree(root, sub) or is_subtree(root.left, sub) or is_subtree(root.right, sub)
Each pair of examples printed True False: [1, 2, 3] against itself and [1, 2] against [1, null, 2]; [1, 2, 2, 3, 4, 4, 3] and [1, 2, 2, null, 3, null, 3]; [4, 1, 2] inside [3, 4, 5, 1, 2] and inside the same tree with an extra 0 under the 2. Subtree is O(n · m), a comparison started at each of n nodes.
Children Sum in a Binary Tree is a check at every node: each node with children must equal their sum, a missing child counting as 0:
def children_sum(node):
if node is None or (node.left is None and node.right is None):
return True # an empty tree and a leaf both pass
kids = (node.left.val if node.left else 0) + (node.right.val if node.right else 0)
return node.val == kids and children_sum(node.left) and children_sum(node.right)
It returned True False for [35, 20, 15, 15, 5, 10, 5] and [1, 4, 3, 5].
Finding duplicates: a name for every subtree
Find Duplicate Subtrees wants every subtree that appears more than once, same shape and same values. Give every subtree a name built from its children's names, bottom up, and count the names. The obvious name is the subtree written out as a string, like (#,4,#) for a leaf 4. It works, but each string is as long as its subtree, so a deep tree builds O(n²) characters of names. On chains with a leaf off every node:
| Nodes | Characters in the names | Strings | Small ids |
|---|---|---|---|
| 2,000 | 6,014,000 | 9.4 ms | 1.53 ms |
| 4,000 | 24,028,000 | 32.9 ms | 3.06 ms |
| 8,000 | 96,056,000 | 122.3 ms | 6.20 ms |
The ids are the fix: a subtree is fully described by its left subtree, its value and its right subtree, so give each distinct (left id, value, right id) triple a number. A name is then three small numbers, whatever the subtree's size:
from collections import defaultdict
def find_duplicate_subtrees(root):
ids, count, duplicates = {}, defaultdict(int), []
def key(node):
"""A small id for this subtree's shape and values, made from its children's ids."""
if node is None:
return 0
triple = (key(node.left), node.val, key(node.right))
if triple not in ids:
ids[triple] = len(ids) + 1 # first time this shape and these values appear
k = ids[triple]
count[k] += 1
if count[k] == 2: # report each repeated subtree once
duplicates.append(node)
return k
key(root)
return duplicates
On the problem's three examples it returned roots whose subtrees read [[4], [2, 4]], [[1]], [[3], [2, 3]], smaller ones first because the names are made bottom up; the problem accepts any order. Each node is named once, O(n).
Spotting it, and when it breaks
The clues. An answer at every node built from its children's answers (heights, sizes, counts, "is it balanced"): return it. "The longest path", "the maximum path sum", "between any two nodes": return a one-sided value and keep the answer beside the calls. "From the root", "on the path", "good nodes": pass it down. "Two trees", "mirror", "same": recurse on both at once. "Duplicate", "same shape": name every subtree.
The near-misses. Anything level by level, or nearest to the root, is level order (Tree Traversals: Depth-First and Breadth-First). A path that has to pass through a given node, or a distance between two given nodes, needs the lowest common ancestor or parent links (Views, Ancestors and Distances). Answers that combine a choice at every node, like robbing houses arranged as a tree, return two values per node and belong to Dynamic Programming.
When it breaks. Every recursion here goes as deep as the tree, with the limits measured in Introduction to Binary Trees. Recomputing a subtree's answer instead of returning it makes a deep tree quadratic, as the diameter and Path Sum III tables show. And names that grow with their subtree do the same.
Bugs that cost a submission
Checking balance only at the root.
def height(node):
return 0 if node is None else 1 + max(height(node.left), height(node.right))
def is_balanced(root):
if root is None:
return True
return abs(height(root.left) - height(root.right)) <= 1 # wrong: only the root is checked
On [1, 2, 2, 3, null, null, 3, 4, null, null, 4] it returned True; the answer is False. Both of the root's subtrees have height 3, and the imbalance is one level down. Check every node, which the −1 does in one pass.
Counting the diameter in nodes.
def diameter(root):
"""The longest path between two nodes, in edges."""
best = 0
def height_through(node):
nonlocal best
if node is None:
return 0
left, right = height_through(node.left), height_through(node.right)
best = max(best, left + right + 1) # wrong: counts the nodes on the path
return 1 + max(left, right) # the parent can use one side only
height_through(root)
return best
On [1, 2, 3, 4, 5] it returned 4; the answer is 3. The problem counts edges, and a path of k nodes has k − 1 of them.
Handing the parent a path that forks.
def max_path_sum(root):
best = root.val # not 0: every value may be negative
def gain(node):
"""The best sum of a path going down from node, which the parent can extend."""
nonlocal best
if node is None:
return 0
left = max(gain(node.left), 0) # a side that loses is left out
right = max(gain(node.right), 0)
best = max(best, node.val + left + right) # the best path that bends here
return node.val + left + right # wrong: hands the parent a path that forks
gain(root)
return best
On [1, 2, 3, 4, 5] it returned 15; the answer is 11. The 2 handed up 4 + 2 + 5, and the root added both sides again: a path that splits at 2 and at 1, which isn't a path.
Starting the best at 0.
def max_path_sum(root):
best = 0 # wrong: assumes some path is at least 0
def gain(node):
"""The best sum of a path going down from node, which the parent can extend."""
nonlocal best
if node is None:
return 0
left = max(gain(node.left), 0) # a side that loses is left out
right = max(gain(node.right), 0)
best = max(best, node.val + left + right) # the best path that bends here
return node.val + max(left, right) # going up, a path takes one side
gain(root)
return best
On [-3] it returned 0; the answer is −3. No path has sum 0 there, and starting at 0 invents one. Start at the root's value.
A mirror that compares the wrong pairs.
def same_tree(p, q):
if p is None or q is None:
return p is q # both empty, or one missing: a mismatch
return p.val == q.val and same_tree(p.left, q.left) and same_tree(p.right, q.right)
def is_symmetric(root):
def mirror(a, b):
if a is None or b is None:
return a is b
return a.val == b.val and mirror(a.left, b.left) and mirror(a.right, b.right) # wrong: not a mirror
return root is None or mirror(root.left, root.right)
def is_subtree(root, sub):
if root is None:
return False
return same_tree(root, sub) or is_subtree(root.left, sub) or is_subtree(root.right, sub)
On [1, 2, 2, 3, 4, 4, 3], which is symmetric, it returned False: it compared left with left, which is the test for Same Tree. A mirror pairs the outside with the outside.
Leaving a running sum in the map on the way back up.
from collections import defaultdict
def path_sum(root, target):
"""Downward paths that sum to target: a prefix equal to total - target, on the way down, starts one."""
seen = defaultdict(int)
seen[0] = 1 # the empty prefix, for paths that start at the root
def walk(node, total):
if node is None:
return 0
total += node.val
count = seen[total - target] # paths that end here
seen[total] += 1
count += walk(node.left, total) + walk(node.right, total)
return count
return walk(root, 0)
On [1, 2, 4] with target 2 it returned 2; the answer is 1, the 2 on its own. The left branch's running sum, 3, was still in the map when the walk reached the 4 on the right, and 5 − 2 = 3 counted a path that jumps between branches.
Check yourself
Quiz
1 / 6Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Practice problems
In this order:
- Same Tree: two trees, one recursion.
- Symmetric Tree: the outside pair and the inside pair.
- Balanced Binary Tree: the height, or −1.
- Diameter of Binary Tree: return the height, keep the bend.
- Subtree of Another Tree: Same Tree at every node.
- Binary Tree Paths: the path goes down as an argument.
- Count Good Nodes in Binary Tree: the largest value above, passed down.
- Children Sum in a Binary Tree: a check at every node.
- Binary Tree Maximum Path Sum: one side up, both sides in the best.
- Path Sum III: running sums on the path.
- Find Duplicate Subtrees: a small name for every subtree.
Next, Views, Ancestors and Distances: columns, ancestors, and moving up as well as down.