How Many Steps Separate Two Nodes
Solve this ProblemYou are given the root of a binary tree with distinct node values, and two values a and b that both appear in the tree. Return the distance between the two nodes: the number of parent-child connections on the unique path that joins them. That path may go up from one node and then down to the other. If a and b are the same node the distance is 0.
You can treat the tree as an undirected graph and run a breadth-first search, or notice that the path always turns at the lowest shared ancestor, so the distance is the sum of the two depths measured from it.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
2 ≤ number of nodes ≤ 100, and every node value is distinct, 1 ≤ node.val ≤ 1000 - ◆
a and b are values that both exist in the tree (they may be equal) - ◆
The tree is given as its root node; each node has a val, a left child and a right child - ◆
The distance between two nodes is the number of parent-child connections (edges) on the unique path between them; that path may go up and then down. Return the distance between the a-node and the b-node (0 if they are the same node)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Treat the Tree as a Graph and Search From a
GoodA tree is a graph with edges in both directions: from every node you can go down to its children AND up to its parent. Build an adjacency list from all parent-child pairs. Then run a breadth-first search starting from a, recording each node's distance from a; the first time b is reached, its distance is the answer (BFS reaches nodes in order of increasing distance). It is easy and general, but it builds a map of all n nodes and a distance table: O(n) time and O(n) space.
O(n)O(n)1class Solution {
2 public int distanceBetween(TreeNode root, int a, int b) {
3 Map<Integer, List<Integer>> links = new HashMap<>();
4 connect(root, links);
5 Map<Integer, Integer> dist = new HashMap<>();
6 Queue<Integer> queue = new ArrayDeque<>();
7 dist.put(a, 0);
8 queue.add(a);
9 while (!queue.isEmpty()) {
10 int cur = queue.poll();
11 if (cur == b) return dist.get(cur);
12 for (int next : links.getOrDefault(cur, new ArrayList<>())) {
13 if (!dist.containsKey(next)) {
14 dist.put(next, dist.get(cur) + 1);
15 queue.add(next);
16 }
17 }
18 }
19 return -1;
20 }
21
22 private void connect(TreeNode node, Map<Integer, List<Integer>> links) {
23 if (node == null) return;
24 for (TreeNode child : new TreeNode[]{node.left, node.right}) {
25 if (child == null) continue;
26 links.computeIfAbsent(node.val, k -> new ArrayList<>()).add(child.val);
27 links.computeIfAbsent(child.val, k -> new ArrayList<>()).add(node.val);
28 connect(child, links);
29 }
30 }
31}Optimal — Lowest Shared Ancestor, Then Measure Both Depths From It
OptimalThe path between a and b always goes up from a to their lowest shared ancestor and then down to b. So find that ancestor with the one-pass recursion (a node returns itself when it is a or b, both children reporting a hit means this node is the meeting point). Then the distance is simply: (edges from the ancestor down to a) + (edges from the ancestor down to b). Each of those depths comes from a plain depth-first search below the ancestor. Three walks of at most n nodes, and only recursion space: O(n) time and O(h) space — no maps, no parent links.
O(n)O(h)1class Solution {
2 public int distanceBetween(TreeNode root, int a, int b) {
3 TreeNode top = meet(root, a, b);
4 return depthOf(top, a, 0) + depthOf(top, b, 0);
5 }
6
7 private TreeNode meet(TreeNode node, int a, int b) {
8 if (node == null || node.val == a || node.val == b) return node;
9 TreeNode left = meet(node.left, a, b);
10 TreeNode right = meet(node.right, a, b);
11 if (left != null && right != null) return node;
12 return left != null ? left : right;
13 }
14
15 private int depthOf(TreeNode node, int target, int depth) {
16 if (node == null) return -1;
17 if (node.val == target) return depth;
18 int left = depthOf(node.left, target, depth + 1);
19 if (left != -1) return left;
20 return depthOf(node.right, target, depth + 1);
21 }
22}