Paths, Lowest Common Ancestor and Building from Traversals
28 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Many tree problems ask about routes: a path to a leaf, the meeting point of two nodes, or a tree that must be rebuilt from lists. Each one is a recursion that passes information down, brings an answer up, or both.
Root-to-leaf paths
Root-to-leaf path is a route that starts at the root, follows child links downward and ends at a leaf. A tree has exactly one such path for each leaf.
A path starts at the root and goes down. Hand each call the path so far. When a node has no children, the path is complete. A string is a good carrier, because each call gets its own copy.
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))def paths(node, prefix=""): if node: prefix += str(node.val) if not node.left and not node.right: yield prefix yield from paths(node.left, prefix + "->") yield from paths(node.right, prefix + "->")print(list(paths(root)))Example 1 · Paths with a list that is undone
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
def collect(node, path, result): if node is None: return path.append(node.val) if not node.left and not node.right: result.append(path[:]) collect(node.left, path, result) collect(node.right, path, result) path.pop()
result = []collect(root, [], result)print(result)[[1, 2, 4], [1, 2, 5], [1, 3, 6]]
What this code does
- One list is shared by all calls, so each call must remove its value with
pop()before returning. This is called backtracking. path[:]stores a copy, because the shared list keeps changing.
prefix + "->" makes a new string for each child, so nothing has to be undone afterwards. Time is O(n) times the path length, because every path is copied.
Does a path add up to a target?
Instead of adding values, subtract each value from the target on the way down. At a leaf, the path works when nothing is left. The check must happen only at leaves, because a half path does not count.
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))def has_path_sum(node, target): if node is None: return False target -= node.val if not node.left and not node.right: return target == 0 return has_path_sum(node.left, target) or has_path_sum(node.right, target)print(has_path_sum(root, 7), has_path_sum(root, 9))Example 2 · Count downward paths with a given sum: slow
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
def from_here(node, target): if node is None: return 0 target -= node.val return (target == 0) + from_here(node.left, target) + from_here(node.right, target)
def count_paths(node, target): if node is None: return 0 return from_here(node, target) + count_paths(node.left, target) + count_paths(node.right, target)
root = TreeNode(10, TreeNode(5, TreeNode(3, TreeNode(3), TreeNode(-2)), TreeNode(2, None, TreeNode(1))), TreeNode(-3, None, TreeNode(11)))print(count_paths(root, 8))3
What this code does
- A path may start at any node and must go downward. The slow way starts a fresh search at every node.
- The three paths are 5 and 3, 5 and 2 and 1, and -3 and 11. Time is O(n times h), or O(n squared) on a chain.
Example 3 · Count downward paths with a given sum: one pass
from collections import Counterclass TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
def count_paths(root, target): seen = Counter({0: 1})
def walk(node, running): if node is None: return 0 running += node.val found = seen[running - target] seen[running] += 1 found += walk(node.left, running) + walk(node.right, running) seen[running] -= 1 return found
return walk(root, 0)
root = TreeNode(10, TreeNode(5, TreeNode(3, TreeNode(3), TreeNode(-2)), TreeNode(2, None, TreeNode(1))), TreeNode(-3, None, TreeNode(11)))print(count_paths(root, 8))3
What this code does
seencounts the running sums on the current path from the root. An earlier sum equal torunning - targetmarks a start point of a path that ends here.- After both children are done the sum is removed again. Time is O(n), the same idea as prefix sums on a list.
The paths sum to 7, 8 and 10, so 7 is found and 9 is not. or stops at the first success. Time is O(n) and stack space is O(h).
Lowest common ancestor
Lowest common ancestor of two nodes is the deepest node that has both of them in its subtree. A node counts as part of its own subtree, so a node can be the ancestor of itself and another node.
Two nodes share many ancestors. The lowest one is the answer. Search both sides for p and q. If one side finds p and the other finds q, the current node is where the two routes meet.
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))def lca(node, p, q): if node is None or node.val in (p, q): return node left, right = lca(node.left, p, q), lca(node.right, p, q) return node if left and right else left or rightprint(lca(root, 4, 5).val, lca(root, 4, 6).val, lca(root, 2, 4).val)Example 4 · LCA in a search tree
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
root = TreeNode(6, TreeNode(2, TreeNode(0), TreeNode(4)), TreeNode(8, TreeNode(7), TreeNode(9)))
def lca_bst(root, p, q): node = root while node: if p < node.val and q < node.val: node = node.left elif p > node.val and q > node.val: node = node.right else: return node.val
print(lca_bst(root, 0, 4), lca_bst(root, 0, 9), lca_bst(root, 7, 9))2 6 8
What this code does
- In a search tree the values tell which side to go. The first node that separates p and q, or equals one of them, is the answer.
- It needs no recursion and costs O(h) time and O(1) space.
Example 5 · LCA from two paths
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
def path_to(node, target): if node is None: return None if node.val == target: return [node.val] for child in (node.left, node.right): found = path_to(child, target) if found: return [node.val] + found
answer = Nonefor a, b in zip(path_to(root, 4), path_to(root, 6)): if a != b: break answer = aprint(path_to(root, 4), path_to(root, 6), answer)[1, 2, 4] [1, 3, 6] 1
What this code does
- Find the route from the root to each node, then keep the last value that both routes share.
- It takes two passes and O(h) extra space for the routes. The single recursive pass is shorter.
A node may be its own ancestor, so the answer for 2 and 4 is 2. The code assumes both values exist and are unique. It visits each node once, so time is O(n).
Build a tree from two traversals
Preorder starts with the root. Find that value in the inorder list: everything before it is the left subtree and everything after it is the right subtree. Repeat on each side. A dictionary finds positions in O(1).
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightdef build_tree(preorder, inorder): index = {v: i for i, v in enumerate(inorder)} it = iter(preorder) def make(lo, hi): if lo > hi: return None root = TreeNode(next(it)) root.left = make(lo, index[root.val] - 1) root.right = make(index[root.val] + 1, hi) return root return make(0, len(inorder) - 1)print(build_tree([1, 2, 4, 5, 3, 6], [4, 2, 5, 1, 3, 6]).right.right.val)Example 6 · Build from traversals the simple way
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
def build_tree(pre, ino): if not pre: return None mid = ino.index(pre[0]) return TreeNode(pre[0], build_tree(pre[1:mid + 1], ino[:mid]), build_tree(pre[mid + 1:], ino[mid + 1:]))
def postorder(node): return postorder(node.left) + postorder(node.right) + [node.val] if node else []
print(postorder(build_tree([1, 2, 4, 5, 3, 6], [4, 2, 5, 1, 3, 6])))[4, 5, 2, 6, 3, 1]
What this code does
- This is easy to read.
indexsearches the list and slicing copies it, so time is O(n squared) in the worst case. - The dictionary and iterator version in the lesson removes both costs.
The iterator it hands out the preorder values one by one, in exactly the order the roots are needed. Left is built before right, as in preorder. Time and space are O(n).
A path that bends: maximum path sum
A path may start and end at any node. At each node, the best bent path is the node plus the better downward gains from the left and right. Ignore a branch whose gain is negative. Keep the best seen.
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightdef max_path(root): best = float("-inf") def gain(node): nonlocal best if node is None: return 0 left, right = max(gain(node.left), 0), max(gain(node.right), 0) best = max(best, node.val + left + right) return node.val + max(left, right) gain(root) return bestprint(max_path(TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))))Example 7 · Maximum path sum when everything is negative
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
def max_path(root): best = float("-inf")
def gain(node): nonlocal best if node is None: return 0 left, right = max(gain(node.left), 0), max(gain(node.right), 0) best = max(best, node.val + left + right) return node.val + max(left, right)
gain(root) return best
print(max_path(TreeNode(-3, TreeNode(-2), TreeNode(-1))))-1
What this code does
- Starting
bestat zero would wrongly report 0. Starting at minus infinity gives the best single node, -1. max(gain, 0)drops a branch that would lower the sum, but the node itself must always be on the path.
Example 8 · Back to level-order text
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
def to_tokens(root): tokens, queue = [], [root] for node in queue: tokens.append(str(node.val) if node else "null") if node: queue += [node.left, node.right] while tokens[-1] == "null": tokens.pop() return " ".join(tokens)
print(to_tokens(root))1 2 3 4 5 null 6
What this code does
- Appending to a list while looping over it makes a queue without
deque. Missing children becomenull, and trailing nulls are dropped. - This is the reverse of the builder from the first lesson. The output reads the same as the input.
The best path is 15, 20, 7 and sums to 42. The function returns only a one-sided gain, because a parent can extend a path in one direction. This is the same shape as the diameter.
Next step
Check your understanding
12 quick questions