423. Distance Between Two Nodes in a Binary Tree

Given a binary tree and two values p and q that both exist in it, print the number of edges on the path between them.

Input: The first line contains space-separated level-order tokens ('N' for missing children) describing the binary tree. The second line contains two integers p and q, both guaranteed to exist in the tree. Output: Print a single integer - the number of edges on the path between p and q.

1 <= number of nodes <= 10^5

A node's distance to ITSELF is 0 (the LCA of a node with itself is the node, and its depth from itself is 0) - a trivial but easy edge case to verify your logic handles correctly.

Find the number of edges on the path connecting two given nodes in a binary tree. Brute force: Find the full root-to-p path and root-to-q path separately, then figure out where they diverge and count the remaining edges on each side - this works but requires more bookkeeping (storing full paths) than directly computing depths relative to the LCA. Optimised: Once the LCA is found (using the standard general binary-tree LCA algorithm), computing each node's depth relative to THAT LCA (via a small additional DFS from the LCA) directly gives the distance as a simple sum - no need to store or compare full root-to-node paths explicitly.

Do two separate traversals from the root to build the full list of nodes on the path from the root to p, and the full list from the root to q, then walk both lists together to find the last node they have in common - the lowest common ancestor (LCA). The distance is then the number of steps from the LCA down to p plus the number of steps from the LCA down to q. This exploits the tree structure directly, unlike the generic BFS, but requires storing both full paths explicitly. Time: O(n) Space: O(n)

Use one recursive traversal that, for each subtree, reports whether p and/or q were found within it and, as soon as both are found in different branches of the same node, that node is identified as the LCA; depths of p and q are tracked alongside this same recursion. The distance is then depth(p) + depth(q) - 2*depth(LCA). This finds everything needed in a single traversal without ever materializing the full root-to-node path lists, using only recursion-stack space proportional to the tree's height rather than storing O(n) explicit paths. Time: O(n) Space: O(h)

Treat the binary tree as an ordinary undirected graph (each parent-child link works both ways) and run a breadth-first search starting from node p, counting edges level by level until node q is reached; the level at which q is found is the answer. This works for any two nodes in any tree because it ignores the tree's specific structure entirely and just measures shortest-path distance directly, but it doesn't take advantage of tree properties like a unique root-to-node path, so it does more work than necessary. Time: O(n) Space: O(n)

1. Find the Lowest Common Ancestor (LCA) of the two given nodes first. 2. Compute each node's DEPTH measured specifically FROM the LCA (not from the tree's actual root). 3. The total distance is simply depth(p from LCA) + depth(q from LCA).

Time: O(n) - finding the LCA costs O(n) in the worst case, and computing each node's depth from the LCA is also linear. Space: O(h) for the recursion stack(s) involved.

Test p equal to q (distance 0), one value being an ancestor of the other (their LCA is one of the two nodes itself), and n=10^5 nodes for performance.

Be ready to explain WHY the path between any two nodes must always pass through their LCA - this is the foundational insight that makes the whole 'find LCA, then sum two depths' approach correct.