Min distance between two given nodes of a Binary Tree | Practice Medium 0 attempts
GeeksforGeeks ↗

Min distance between two given nodes of a Binary Tree | Practice

Medium TreeBinary TreeDFS GeeksforGeeks

You're given a binary tree along with two node values a and b known to exist in the tree. Values in the tree are unique. Find the distance between them, measured as the number of edges on the path connecting the two nodes — typically found by locating their lowest common ancestor and summing the edges from it down to each node.

Input Format
Implement findDist(root, a, b). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
root = [1,2,3,4,5,6,7]
a = 4
b = 6
Output
4

Example 2

Input
root = [1,2,3]
a = 2
b = 2
Output
0
Constraints
  • 1 <= N <= 10^4
  • 1 <= a, b <= N
Test Cases (2)
Case 1
Args: [[1,2,3,4,5,6,7],4,6] Expected: 4
Case 2
Args: [[1,2,3],2,2] Expected: 0
Topics
TreeBinary TreeDFS

Parent Map and Ancestor Distances

Record parent pointers, then map the distance from a to each ancestor. Walk upward from b until reaching one of those ancestors; add the two distances.

javascript
function findDist(root, a, b) {
  const parent=new Map([[root,null]]),stack=[root];let an,bn;
  while(stack.length){const node=stack.pop();if(node.val===a)an=node;if(node.val===b)bn=node;for(const child of [node.left,node.right])if(child){parent.set(child,node);stack.push(child);}}
  const distance=new Map();let d=0;while(an){distance.set(an,d++);an=parent.get(an);}
  d=0;while(!distance.has(bn)){bn=parent.get(bn);d++;}
  return d+distance.get(bn);
}

Time: O(n) | Space: O(n) auxiliary space, excluding output

Saved in this browser only. Private to you.

JavaScript