24.06Intermediate / Advanced5 topics17 min5 interactive animations

Path problems

Path problems on trees: root-to-leaf paths, path sums, lowest common ancestor, the distance between two nodes and the boundary traversal.

Learning goals

Collect root-to-leaf paths with choose-explore-unchoose
Decide a root-to-leaf sum with a shrinking target
Find a lowest common ancestor in one pass
Compute distances through the lowest common ancestor
Produce the boundary of a tree in anticlockwise order

Prerequisites

Structural computationsBacktracking and constraint search

A path in a tree is unique, so path problems are cleaner than in graphs. They are depth-first searches where the current path is a piece of state, and the choose-explore-unchoose pattern of backtracking applies directly.

24.06.1

Root-to-leaf paths

To list every root-to-leaf path, keep the current path in a list: add the node on the way down (**choose**), record a copy when a leaf is reached, recurse into both children (**explore**), and remove the node on the way up (**unchoose**). A tree has one path per leaf. In the first preset, “1 2 3 # 5” has the 2 paths 1→2→5 and 1→3.

The same shape appears in the backtracking chapter; here the 'options' at each node are simply the two children, so the search never repeats a state and needs no pruning.

Java

1static List<String> rootToLeaf(TreeNode root) {
2    List<String> out = new ArrayList<>();
3    walk(root, new ArrayList<>(), out);
4    return out;
5}
6static void walk(TreeNode n, List<Integer> path, List<String> out) {
7    if (n == null) return;
8    path.add(n.val);                                 // choose
9    if (n.left == null && n.right == null) out.add(path.toString());
10    else { walk(n.left, path, out); walk(n.right, path, out); }
11    path.remove(path.size() - 1);                    // unchoose
12}

Best

O(n)

Average

O(n · h)

Worst

O(n²)

Space

O(h) plus the output

Path problems: root-to-leaf paths, path sum, lowest common ancestor, distance, boundary

Interactive · edit the input

binary tree · 9 nodes

Current nodeCurrent pathAnswerFinishedLeft boundary / path to aRight boundary / path to b

Setup

Path sum: is there a root-to-leaf path adding up to 22?

Step 1 / 9

Java

1static void paths(TreeNode n, List<Integer> path, List<String> out) {
2    if (n == null) return;
3    path.add(n.val);                             // choose
4    if (n.left == null && n.right == null) out.add(path.toString());
5    else { paths(n.left, path, out); paths(n.right, path, out); }
6    path.remove(path.size() - 1);                // unchoose
7}
8static boolean hasPathSum(TreeNode n, int remaining) {
9    if (n == null) return false;
10    remaining -= n.val;
11    if (n.left == null && n.right == null) return remaining == 0;   // only a leaf ends a root-to-leaf path
12    return hasPathSum(n.left, remaining) || hasPathSum(n.right, remaining);
13}
14static TreeNode lca(TreeNode n, int a, int b) {
15    if (n == null || n.val == a || n.val == b) return n;
16    TreeNode l = lca(n.left, a, b), r = lca(n.right, a, b);
17    return l != null && r != null ? n : (l != null ? l : r);   // both sides found one: n splits them
18}
19static int distance(TreeNode root, int a, int b) {
20    TreeNode m = lca(root, a, b);
21    return depth(m, a, 0) + depth(m, b, 0);      // edges from the LCA down to each node
22}
23static int depth(TreeNode n, int v, int d) {
24    if (n == null) return -1;
25    if (n.val == v) return d;
26    int l = depth(n.left, v, d + 1);
27    return l >= 0 ? l : depth(n.right, v, d + 1);
28}
29static List<Integer> boundary(TreeNode root) {   // anticlockwise from the root
30    List<Integer> out = new ArrayList<>();
31    if (root == null) return out;
32    if (!isLeaf(root)) out.add(root.val);
33    for (TreeNode n = root.left; n != null && !isLeaf(n); n = n.left != null ? n.left : n.right) out.add(n.val);   // left edge
34    addLeaves(root, out);                        // all leaves, left to right
35    Deque<Integer> right = new ArrayDeque<>();
36    for (TreeNode n = root.right; n != null && !isLeaf(n); n = n.right != null ? n.right : n.left) right.push(n.val);
37    out.addAll(right);                           // right edge, bottom to top
38    return out;
39}
40static boolean isLeaf(TreeNode n) { return n.left == null && n.right == null; }
41static void addLeaves(TreeNode n, List<Integer> out) {
42    if (n == null) return;
43    if (isLeaf(n)) out.add(n.val);
44    addLeaves(n.left, out); addLeaves(n.right, out);
45}

Live state

problem

Path sum

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L8	problem=Path sum	Path sum: is there a root-to-leaf path adding up to 22?
2	L10	remaining=17	Take 5: 22 - 5 = 17 still to find.
3	L10	remaining=13	Take 4: 17 - 4 = 13 still to find.
4	L10	remaining=2	Take 11: 13 - 11 = 2 still to find.
5	L10	remaining=-5	Take 7: 2 - 7 = -5 still to find.
6	L11	remaining=-5	7 is a leaf but -5 remains: this path does not work.
7	L10	remaining=0	Take 2: 2 - 2 = 0 still to find.
8	L11	remaining=0	2 is a leaf and nothing remains: the path 5 → 4 → 11 → 2 adds up to 22.
9	L12	result=true	true: 5 + 4 + 11 + 2 = 22.

24.06.2

Path sum

'Is there a root-to-leaf path with sum S?' subtracts each node's value from the target on the way down and asks the question again of the children. Only a **leaf** with exactly 0 remaining answers yes: a partial path that reaches the target at an internal node does not count.

The “Path sum 22 (exists)” preset finds 5 + 4 + 11 + 2 = 22. The “Path sum 9 (reached early: no)” preset shows 5 + 4 = 9 at node 4, which is internal, so the search continues and answers false after trying every leaf. The recursion short-circuits as soon as one side returns true.

Java

1static boolean hasPathSum(TreeNode n, int remaining) {
2    if (n == null) return false;
3    remaining -= n.val;
4    if (n.left == null && n.right == null) return remaining == 0;   // only a leaf ends a path
5    return hasPathSum(n.left, remaining) || hasPathSum(n.right, remaining);
6}

Best

O(h)

Average

O(n)

Worst

O(n)

Space

O(h)

Path problems: root-to-leaf paths, path sum, lowest common ancestor, distance, boundary

Interactive · edit the input

binary tree · 9 nodes

Current nodeCurrent pathAnswerFinishedLeft boundary / path to aRight boundary / path to b

Setup

Path sum: is there a root-to-leaf path adding up to 22?

Step 1 / 9

Java

1static void paths(TreeNode n, List<Integer> path, List<String> out) {
2    if (n == null) return;
3    path.add(n.val);                             // choose
4    if (n.left == null && n.right == null) out.add(path.toString());
5    else { paths(n.left, path, out); paths(n.right, path, out); }
6    path.remove(path.size() - 1);                // unchoose
7}
8static boolean hasPathSum(TreeNode n, int remaining) {
9    if (n == null) return false;
10    remaining -= n.val;
11    if (n.left == null && n.right == null) return remaining == 0;   // only a leaf ends a root-to-leaf path
12    return hasPathSum(n.left, remaining) || hasPathSum(n.right, remaining);
13}
14static TreeNode lca(TreeNode n, int a, int b) {
15    if (n == null || n.val == a || n.val == b) return n;
16    TreeNode l = lca(n.left, a, b), r = lca(n.right, a, b);
17    return l != null && r != null ? n : (l != null ? l : r);   // both sides found one: n splits them
18}
19static int distance(TreeNode root, int a, int b) {
20    TreeNode m = lca(root, a, b);
21    return depth(m, a, 0) + depth(m, b, 0);      // edges from the LCA down to each node
22}
23static int depth(TreeNode n, int v, int d) {
24    if (n == null) return -1;
25    if (n.val == v) return d;
26    int l = depth(n.left, v, d + 1);
27    return l >= 0 ? l : depth(n.right, v, d + 1);
28}
29static List<Integer> boundary(TreeNode root) {   // anticlockwise from the root
30    List<Integer> out = new ArrayList<>();
31    if (root == null) return out;
32    if (!isLeaf(root)) out.add(root.val);
33    for (TreeNode n = root.left; n != null && !isLeaf(n); n = n.left != null ? n.left : n.right) out.add(n.val);   // left edge
34    addLeaves(root, out);                        // all leaves, left to right
35    Deque<Integer> right = new ArrayDeque<>();
36    for (TreeNode n = root.right; n != null && !isLeaf(n); n = n.right != null ? n.right : n.left) right.push(n.val);
37    out.addAll(right);                           // right edge, bottom to top
38    return out;
39}
40static boolean isLeaf(TreeNode n) { return n.left == null && n.right == null; }
41static void addLeaves(TreeNode n, List<Integer> out) {
42    if (n == null) return;
43    if (isLeaf(n)) out.add(n.val);
44    addLeaves(n.left, out); addLeaves(n.right, out);
45}

Live state

problem

Path sum

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L8	problem=Path sum	Path sum: is there a root-to-leaf path adding up to 22?
2	L10	remaining=17	Take 5: 22 - 5 = 17 still to find.
3	L10	remaining=13	Take 4: 17 - 4 = 13 still to find.
4	L10	remaining=2	Take 11: 13 - 11 = 2 still to find.
5	L10	remaining=-5	Take 7: 2 - 7 = -5 still to find.
6	L11	remaining=-5	7 is a leaf but -5 remains: this path does not work.
7	L10	remaining=0	Take 2: 2 - 2 = 0 still to find.
8	L11	remaining=0	2 is a leaf and nothing remains: the path 5 → 4 → 11 → 2 adds up to 22.
9	L12	result=true	true: 5 + 4 + 11 + 2 = 22.

24.06.3

Lowest common ancestor basics

The **lowest common ancestor** (LCA) of two nodes p and q is the deepest node that has both of them in its subtree (a node counts as its own descendant). One recursive pass finds it: return the node itself if it is p or q; otherwise ask both subtrees. If both sides return something, this node is where the two paths split, so it is the LCA; if only one does, pass that result up.

For the tree “3 5 1 6 2 0 8 # # 7 4” the LCA of 7 and 4 is 2, and the LCA of 5 and 4 is 5 itself: node 5 is above 4, so the search stops at 5 and never looks below it. The animation prints the value returned by every call under its node.

Java

1static TreeNode lca(TreeNode n, int p, int q) {
2    if (n == null || n.val == p || n.val == q) return n;
3    TreeNode l = lca(n.left, p, q), r = lca(n.right, p, q);
4    return l != null && r != null ? n : (l != null ? l : r);   // both sides found one: n splits them
5}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h)

Path problems: root-to-leaf paths, path sum, lowest common ancestor, distance, boundary

Interactive · edit the input

binary tree · 9 nodes

Current nodeCurrent pathAnswerFinishedLeft boundary / path to aRight boundary / path to b

Setup

Path sum: is there a root-to-leaf path adding up to 22?

Step 1 / 9

Java

1static void paths(TreeNode n, List<Integer> path, List<String> out) {
2    if (n == null) return;
3    path.add(n.val);                             // choose
4    if (n.left == null && n.right == null) out.add(path.toString());
5    else { paths(n.left, path, out); paths(n.right, path, out); }
6    path.remove(path.size() - 1);                // unchoose
7}
8static boolean hasPathSum(TreeNode n, int remaining) {
9    if (n == null) return false;
10    remaining -= n.val;
11    if (n.left == null && n.right == null) return remaining == 0;   // only a leaf ends a root-to-leaf path
12    return hasPathSum(n.left, remaining) || hasPathSum(n.right, remaining);
13}
14static TreeNode lca(TreeNode n, int a, int b) {
15    if (n == null || n.val == a || n.val == b) return n;
16    TreeNode l = lca(n.left, a, b), r = lca(n.right, a, b);
17    return l != null && r != null ? n : (l != null ? l : r);   // both sides found one: n splits them
18}
19static int distance(TreeNode root, int a, int b) {
20    TreeNode m = lca(root, a, b);
21    return depth(m, a, 0) + depth(m, b, 0);      // edges from the LCA down to each node
22}
23static int depth(TreeNode n, int v, int d) {
24    if (n == null) return -1;
25    if (n.val == v) return d;
26    int l = depth(n.left, v, d + 1);
27    return l >= 0 ? l : depth(n.right, v, d + 1);
28}
29static List<Integer> boundary(TreeNode root) {   // anticlockwise from the root
30    List<Integer> out = new ArrayList<>();
31    if (root == null) return out;
32    if (!isLeaf(root)) out.add(root.val);
33    for (TreeNode n = root.left; n != null && !isLeaf(n); n = n.left != null ? n.left : n.right) out.add(n.val);   // left edge
34    addLeaves(root, out);                        // all leaves, left to right
35    Deque<Integer> right = new ArrayDeque<>();
36    for (TreeNode n = root.right; n != null && !isLeaf(n); n = n.right != null ? n.right : n.left) right.push(n.val);
37    out.addAll(right);                           // right edge, bottom to top
38    return out;
39}
40static boolean isLeaf(TreeNode n) { return n.left == null && n.right == null; }
41static void addLeaves(TreeNode n, List<Integer> out) {
42    if (n == null) return;
43    if (isLeaf(n)) out.add(n.val);
44    addLeaves(n.left, out); addLeaves(n.right, out);
45}

Live state

problem

Path sum

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L8	problem=Path sum	Path sum: is there a root-to-leaf path adding up to 22?
2	L10	remaining=17	Take 5: 22 - 5 = 17 still to find.
3	L10	remaining=13	Take 4: 17 - 4 = 13 still to find.
4	L10	remaining=2	Take 11: 13 - 11 = 2 still to find.
5	L10	remaining=-5	Take 7: 2 - 7 = -5 still to find.
6	L11	remaining=-5	7 is a leaf but -5 remains: this path does not work.
7	L10	remaining=0	Take 2: 2 - 2 = 0 still to find.
8	L11	remaining=0	2 is a leaf and nothing remains: the path 5 → 4 → 11 → 2 adds up to 22.
9	L12	result=true	true: 5 + 4 + 11 + 2 = 22.

24.06.4

Distance between nodes

The path between two nodes in a tree goes up to their lowest common ancestor and down again, so distance(p, q) = depth(p) + depth(q) - 2 · depth(lca). Equivalently, add the depth of each node *measured from the LCA*.

For 6 and 4 in the same tree the LCA is 5; 6 is 1 edge below it and 4 is 2 edges below it (through 2), so the distance is 1 + 2 = 3 edges. The animation highlights the two arms in different colours.

Java

1static int distance(TreeNode root, int p, int q) {
2    TreeNode m = lca(root, p, q);
3    return depthFrom(m, p, 0) + depthFrom(m, q, 0);  // edges from the LCA down to each node
4}
5static TreeNode lca(TreeNode n, int p, int q) {
6    if (n == null || n.val == p || n.val == q) return n;
7    TreeNode l = lca(n.left, p, q), r = lca(n.right, p, q);
8    return l != null && r != null ? n : (l != null ? l : r);
9}
10static int depthFrom(TreeNode n, int v, int d) {
11    if (n == null) return -1;
12    if (n.val == v) return d;
13    int l = depthFrom(n.left, v, d + 1);
14    return l >= 0 ? l : depthFrom(n.right, v, d + 1);
15}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h)

Path problems: root-to-leaf paths, path sum, lowest common ancestor, distance, boundary

Interactive · edit the input

binary tree · 9 nodes

Current nodeCurrent pathAnswerFinishedLeft boundary / path to aRight boundary / path to b

Setup

Path sum: is there a root-to-leaf path adding up to 22?

Step 1 / 9

Java

1static void paths(TreeNode n, List<Integer> path, List<String> out) {
2    if (n == null) return;
3    path.add(n.val);                             // choose
4    if (n.left == null && n.right == null) out.add(path.toString());
5    else { paths(n.left, path, out); paths(n.right, path, out); }
6    path.remove(path.size() - 1);                // unchoose
7}
8static boolean hasPathSum(TreeNode n, int remaining) {
9    if (n == null) return false;
10    remaining -= n.val;
11    if (n.left == null && n.right == null) return remaining == 0;   // only a leaf ends a root-to-leaf path
12    return hasPathSum(n.left, remaining) || hasPathSum(n.right, remaining);
13}
14static TreeNode lca(TreeNode n, int a, int b) {
15    if (n == null || n.val == a || n.val == b) return n;
16    TreeNode l = lca(n.left, a, b), r = lca(n.right, a, b);
17    return l != null && r != null ? n : (l != null ? l : r);   // both sides found one: n splits them
18}
19static int distance(TreeNode root, int a, int b) {
20    TreeNode m = lca(root, a, b);
21    return depth(m, a, 0) + depth(m, b, 0);      // edges from the LCA down to each node
22}
23static int depth(TreeNode n, int v, int d) {
24    if (n == null) return -1;
25    if (n.val == v) return d;
26    int l = depth(n.left, v, d + 1);
27    return l >= 0 ? l : depth(n.right, v, d + 1);
28}
29static List<Integer> boundary(TreeNode root) {   // anticlockwise from the root
30    List<Integer> out = new ArrayList<>();
31    if (root == null) return out;
32    if (!isLeaf(root)) out.add(root.val);
33    for (TreeNode n = root.left; n != null && !isLeaf(n); n = n.left != null ? n.left : n.right) out.add(n.val);   // left edge
34    addLeaves(root, out);                        // all leaves, left to right
35    Deque<Integer> right = new ArrayDeque<>();
36    for (TreeNode n = root.right; n != null && !isLeaf(n); n = n.right != null ? n.right : n.left) right.push(n.val);
37    out.addAll(right);                           // right edge, bottom to top
38    return out;
39}
40static boolean isLeaf(TreeNode n) { return n.left == null && n.right == null; }
41static void addLeaves(TreeNode n, List<Integer> out) {
42    if (n == null) return;
43    if (isLeaf(n)) out.add(n.val);
44    addLeaves(n.left, out); addLeaves(n.right, out);
45}

Live state

problem

Path sum

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L8	problem=Path sum	Path sum: is there a root-to-leaf path adding up to 22?
2	L10	remaining=17	Take 5: 22 - 5 = 17 still to find.
3	L10	remaining=13	Take 4: 17 - 4 = 13 still to find.
4	L10	remaining=2	Take 11: 13 - 11 = 2 still to find.
5	L10	remaining=-5	Take 7: 2 - 7 = -5 still to find.
6	L11	remaining=-5	7 is a leaf but -5 remains: this path does not work.
7	L10	remaining=0	Take 2: 2 - 2 = 0 still to find.
8	L11	remaining=0	2 is a leaf and nothing remains: the path 5 → 4 → 11 → 2 adds up to 22.
9	L12	result=true	true: 5 + 4 + 11 + 2 = 22.

24.06.5

Boundary traversal

The **boundary** of a tree, read anticlockwise from the root, is: the root, the **left edge** from top to bottom (without leaves), all the **leaves** from left to right, and the **right edge** from bottom to top (without leaves and without the root). For “20 8 22 4 12 # 25 # # 10 14” the result is [20, 8, 4, 10, 14, 25, 22].

Three details cause most bugs: leaves are added only once, by the leaf pass; the left edge follows the left child but falls back to the right child when there is no left one; and the right edge is collected top to bottom but output reversed.

Java

1static List<Integer> boundary(TreeNode root) {
2    List<Integer> out = new ArrayList<>();
3    if (root == null) return out;
4    if (!isLeaf(root)) out.add(root.val);
5    for (TreeNode n = root.left; n != null && !isLeaf(n); n = n.left != null ? n.left : n.right) out.add(n.val);   // left edge
6    addLeaves(root, out);
7    Deque<Integer> right = new ArrayDeque<>();
8    for (TreeNode n = root.right; n != null && !isLeaf(n); n = n.right != null ? n.right : n.left) right.push(n.val);
9    out.addAll(right);                               // right edge, bottom to top
10    return out;
11}
12static boolean isLeaf(TreeNode n) { return n.left == null && n.right == null; }
13static void addLeaves(TreeNode n, List<Integer> out) {
14    if (n == null) return;
15    if (isLeaf(n)) out.add(n.val);
16    addLeaves(n.left, out);
17    addLeaves(n.right, out);
18}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h)

Path problems: root-to-leaf paths, path sum, lowest common ancestor, distance, boundary

Interactive · edit the input

binary tree · 9 nodes

Current nodeCurrent pathAnswerFinishedLeft boundary / path to aRight boundary / path to b

Setup

Path sum: is there a root-to-leaf path adding up to 22?

Step 1 / 9

Java

1static void paths(TreeNode n, List<Integer> path, List<String> out) {
2    if (n == null) return;
3    path.add(n.val);                             // choose
4    if (n.left == null && n.right == null) out.add(path.toString());
5    else { paths(n.left, path, out); paths(n.right, path, out); }
6    path.remove(path.size() - 1);                // unchoose
7}
8static boolean hasPathSum(TreeNode n, int remaining) {
9    if (n == null) return false;
10    remaining -= n.val;
11    if (n.left == null && n.right == null) return remaining == 0;   // only a leaf ends a root-to-leaf path
12    return hasPathSum(n.left, remaining) || hasPathSum(n.right, remaining);
13}
14static TreeNode lca(TreeNode n, int a, int b) {
15    if (n == null || n.val == a || n.val == b) return n;
16    TreeNode l = lca(n.left, a, b), r = lca(n.right, a, b);
17    return l != null && r != null ? n : (l != null ? l : r);   // both sides found one: n splits them
18}
19static int distance(TreeNode root, int a, int b) {
20    TreeNode m = lca(root, a, b);
21    return depth(m, a, 0) + depth(m, b, 0);      // edges from the LCA down to each node
22}
23static int depth(TreeNode n, int v, int d) {
24    if (n == null) return -1;
25    if (n.val == v) return d;
26    int l = depth(n.left, v, d + 1);
27    return l >= 0 ? l : depth(n.right, v, d + 1);
28}
29static List<Integer> boundary(TreeNode root) {   // anticlockwise from the root
30    List<Integer> out = new ArrayList<>();
31    if (root == null) return out;
32    if (!isLeaf(root)) out.add(root.val);
33    for (TreeNode n = root.left; n != null && !isLeaf(n); n = n.left != null ? n.left : n.right) out.add(n.val);   // left edge
34    addLeaves(root, out);                        // all leaves, left to right
35    Deque<Integer> right = new ArrayDeque<>();
36    for (TreeNode n = root.right; n != null && !isLeaf(n); n = n.right != null ? n.right : n.left) right.push(n.val);
37    out.addAll(right);                           // right edge, bottom to top
38    return out;
39}
40static boolean isLeaf(TreeNode n) { return n.left == null && n.right == null; }
41static void addLeaves(TreeNode n, List<Integer> out) {
42    if (n == null) return;
43    if (isLeaf(n)) out.add(n.val);
44    addLeaves(n.left, out); addLeaves(n.right, out);
45}

Live state

problem

Path sum

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L8	problem=Path sum	Path sum: is there a root-to-leaf path adding up to 22?
2	L10	remaining=17	Take 5: 22 - 5 = 17 still to find.
3	L10	remaining=13	Take 4: 17 - 4 = 13 still to find.
4	L10	remaining=2	Take 11: 13 - 11 = 2 still to find.
5	L10	remaining=-5	Take 7: 2 - 7 = -5 still to find.
6	L11	remaining=-5	7 is a leaf but -5 remains: this path does not work.
7	L10	remaining=0	Take 2: 2 - 2 = 0 still to find.
8	L11	remaining=0	2 is a leaf and nothing remains: the path 5 → 4 → 11 → 2 adds up to 22.
9	L12	result=true	true: 5 + 4 + 11 + 2 = 22.

Practice ladder

Now try it yourself

Easy

Path Sum
Binary Tree Paths
Lowest Common Ancestor of a Binary Search Tree

Medium

Lowest Common Ancestor of a Binary Tree
Path Sum II
Boundary of Binary Tree
Path Sum III

Advanced

All Nodes Distance K in Binary Tree
Binary Tree Maximum Path Sum

Key takeaways

Root-to-leaf paths use choose, recurse, unchoose; a tree has one path per leaf.
A path sum must end at a leaf: reaching the target at an internal node does not count.
The LCA is the first node whose two subtrees both report a target.
distance(p, q) goes through the LCA: the two depths below it add.
Boundary traversal is root, left edge, leaves, right edge reversed, with leaves added once.