Find Distance in a Binary Tree

Find Distance in a Binary Tree

What is this problem about?

The Find Distance in a Binary Tree interview question asks you to find the number of edges on the path between two given nodes $P$ and $Q$ in a binary tree. You are given the values of the two nodes, and you are guaranteed that both exist in the tree.

Why is this asked in interviews?

Amazon and other companies use this "Medium" problem to test your understanding of the Lowest Common Ancestor (LCA) interview pattern. The distance between any two nodes in a tree is defined by their relationship to their common ancestor. It evaluation your proficiency with Depth-First Search (DFS) and your ability to combine results from multiple recursive calls.

Algorithmic pattern used

This problem uses the Lowest Common Ancestor (LCA) pattern. The distance between nodes $P$ and $Q$ is calculated as: dist(Root, P) + dist(Root, Q) - 2 * dist(Root, LCA(P, Q))

1. Find the Lowest Common Ancestor of $P$ and $Q$.
2. Calculate the distance from the LCA to $P$.
3. Calculate the distance from the LCA to $Q$.
4. The sum of these two distances is the total distance.

Example explanation

Tree:

    3
   / 
  5   1
 / 
6   2

Find distance between 6 and 1.

1. LCA(6, 1) is 3.
2. Distance(3, 6): 3 $o$ 5 $o$ 6 (2 edges).
3. Distance(3, 1): 3 $o$ 1 (1 edge). Total Distance = $2 + 1 = 3$.

Common mistakes candidates make

• Calculating from root every time: Trying to find distances from the root without finding the LCA first, which makes it harder to identify the correct path.
• Assuming BFS is necessary: While BFS finds shortest paths in general graphs, in a tree, there is only one simple path between two nodes, so DFS is often more efficient and easier to implement.
• Null checks: Forgetting to handle cases where one node is a descendant of the other (in which case the LCA is one of the nodes).

Interview preparation tip

LCA is a fundamental building block. Once you find the LCA, any "path property" (distance, sum, max value) can be calculated by looking at the two paths from the LCA to the target nodes. Master the $O(N)$ LCA recursive algorithm.