Find Distance Between Two Nodes in a Binary Tree

Problem Statement

Given the root of a binary tree and two target nodes, find the distance (number of edges) between the two nodes.

You are only given root, source, and target. No parent pointers are available.

Constraints

• 2 <= number of nodes <= 10^5
• All node values are unique
• Both source and target are guaranteed to exist in the tree
• Distance = number of edges on the path between the two nodes

Example

Input:

        3
       / \
      5    1
     / \  / \
    6   2 0   8
       / \
      7   4

source = 5, target = 4

Output: 2

Explanation: Path is 5 → 2 → 4, which has 2 edges.

Input: source = 5, target = 1

Output: 2

Explanation: Path is 5 → 3 → 1

What the Interviewer Expects

1. Identify LCA as the key — the distance between two nodes passes through their Lowest Common Ancestor.
2. Formula: distance(source, target) = depth(source) + depth(target) - 2 * depth(LCA)
3. Alternatively: Find LCA, then compute distance from LCA to source + distance from LCA to target.
4. Clean DFS implementation — find LCA in one pass, compute distances in another (or combine into one traversal).
5. Time: O(n), Space: O(h) where h is tree height.

Follow-ups

1. What if the tree is a BST? Can you optimize the LCA finding step?
2. What if you need to answer this query multiple times for different pairs? How would you preprocess?
3. What if parent pointers ARE available? How does your approach simplify?
4. Can you solve this in a single DFS pass without finding LCA separately?