Find Distance in a Binary Tree - Solution & Explanation

Problem Overview: Given the root of a binary tree and two node values p and q, compute the number of edges in the shortest path between them. The distance is the count of edges you must traverse to move from node p to node q.

Approach 1: Path to Root Comparison (O(n) time, O(n) space)

One straightforward strategy stores the path from the root to each target node. Use a Depth-First Search to build two arrays: the path to p and the path to q. Iterate from the beginning of both paths until the nodes diverge. The last common node is the Lowest Common Ancestor (LCA). The distance becomes (len(path_p) - i) + (len(path_q) - i), where i is the divergence index. This approach is easy to reason about and useful when you want explicit root-to-node paths.

Approach 2: Convert Tree to Graph + BFS (O(n) time, O(n) space)

A binary tree does not normally allow upward traversal. Build a parent map using a DFS traversal and store each node's parent in a hash table. After that, treat the tree like an undirected graph. Start a Breadth-First Search from node p. At every step, explore the left child, right child, and parent while tracking visited nodes. BFS guarantees the first time you reach q is through the shortest path. The BFS level count directly represents the distance in edges.

Approach 3: Lowest Common Ancestor + Depth Search (O(n) time, O(h) space)

The most common interview solution finds the Lowest Common Ancestor of nodes p and q in a binary tree. First run a DFS to locate the LCA. Once the LCA is known, run another DFS from the LCA to compute the depth to p and the depth to q. The total distance is the sum of those two depths. This works because every path between two nodes must pass through their LCA. The recursion stack only stores nodes along the current branch, so space depends on tree height h.

Recommended for interviews: The LCA + depth search approach is the one interviewers expect. It shows you understand tree structure and avoids unnecessary parent maps or extra arrays. The BFS-with-parent-map solution is also valid and often easier to implement quickly. Mentioning the path-comparison method first demonstrates your reasoning from brute force to optimal design.