Minimum Distance Between Two Given Nodes of a Binary Tree Solution
Minimum Distance Between Two Given Nodes of a Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Distance Between Two Given Nodes of a Binary Tree is a medium coding problem on depth-first search and trees, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary tree whose node values are all distinct, and two values a and b that both occur in the tree.
Return the distance between the node holding a and the node holding b: the number of edges on the path between them. If a == b the distance is 0.
Example 1
Input: root = [1,2,3], a = 2, b = 3
Output: 2
Explanation: 2 → 1 → 3 is two edges.
Example 2
Input: root = [11,22,33,44,55,66,77], a = 77, b = 22
Output: 3
Explanation: 77 → 33 → 11 → 22: three edges.
Example 3
Input: root = [1,2,null,3,null,4], a = 2, b = 4
Output: 2
Explanation: 4 hangs two levels below 2 on the same branch.
Constraints
1 <= number of nodes <= 10^51 <= Node.val <= 10^5all node values are distincta and b are values of nodes in the tree
Hints for Minimum Distance Between Two Given Nodes of a Binary Tree
Hint 1
The path between two nodes of a tree goes up from one of them to their lowest common ancestor and then down to the other.
Hint 2
Record the root-to-node path for
aand forb. The two paths agree up to the lowest common ancestor and then split.Hint 3
If the paths share their first
knodes, the distance islen(pathA) + len(pathB) - 2k.
How to solve Minimum Distance Between Two Given Nodes of a Binary Tree
Both root-to-node paths begin with the same nodes down to the lowest common ancestor (LCA). Everything after the shared prefix lies on the path between a and b.
Approach
- Find the path of values from the root to
awith a DFS that pushes a node, recurses, and pops it again if the target was not found below it; do the same forb. - Count
k, the length of the common prefix of the two paths. - Return
len(pathA) + len(pathB) - 2k.
Why it works
The last common node of the two paths is the LCA. The path from a to b climbs len(pathA) - k edges from a up to the LCA and descends len(pathB) - k edges to b, and in a tree that path is the only one, so its length is the distance.
Complexity
- Time —
O(n) - Space —
O(h) for the paths and the recursion
Pitfalls
- When one node is an ancestor of the other, the shared prefix is the whole shorter path — the formula still holds.
- With
a == bboth paths are identical and the answer is 0.
Reference solution
Python
from typing import Optional
def findDist(root: Optional[TreeNode], a: int, b: int) -> int:
pa, pb = [], []
_path(root, a, pa)
_path(root, b, pb)
k = 0
while k < len(pa) and k < len(pb) and pa[k] == pb[k]:
k += 1
return len(pa) + len(pb) - 2 * k
def _path(node, t, out):
if node is None:
return False
out.append(node.val)
if node.val == t or _path(node.left, t, out) or _path(node.right, t, out):
return True
out.pop()
return FalseJava
public static int findDist(TreeNode root, int a, int b) {
List<Integer> pa = new ArrayList<>(), pb = new ArrayList<>();
pathTo(root, a, pa);
pathTo(root, b, pb);
int k = 0;
while (k < pa.size() && k < pb.size() && pa.get(k).intValue() == pb.get(k).intValue()) k++;
return pa.size() + pb.size() - 2 * k;
}
static boolean pathTo(TreeNode node, int t, List<Integer> out) {
if (node == null) return false;
out.add(node.val);
if (node.val == t || pathTo(node.left, t, out) || pathTo(node.right, t, out)) return true;
out.remove(out.size() - 1);
return false;
}C++
static bool pathTo(TreeNode* node, int t, vector<int>& out);
int findDist(TreeNode* root, int a, int b) {
vector<int> pa, pb;
pathTo(root, a, pa);
pathTo(root, b, pb);
size_t k = 0;
while (k < pa.size() && k < pb.size() && pa[k] == pb[k]) k++;
return (int) (pa.size() + pb.size() - 2 * k);
}
static bool pathTo(TreeNode* node, int t, vector<int>& out) {
if (!node) return false;
out.push_back(node->val);
if (node->val == t || pathTo(node->left, t, out) || pathTo(node->right, t, out)) return true;
out.pop_back();
return false;
}JavaScript
var findDist = function(root, a, b) {
var pa = [], pb = [];
pathTo(root, a, pa);
pathTo(root, b, pb);
var k = 0;
while (k < pa.length && k < pb.length && pa[k] === pb[k]) k++;
return pa.length + pb.length - 2 * k;
};
function pathTo(node, t, out) {
if (node === null) return false;
out.push(node.val);
if (node.val === t || pathTo(node.left, t, out) || pathTo(node.right, t, out)) return true;
out.pop();
return false;
}Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals