Find Distance Between Two Nodes
You are given the root of a binary tree and two node values, n1 and n2. Your task is to find the distance between the two nodes.
The distance between two nodes is defined as the number of edges on the shortest path connecting them. This path passes through their Lowest Common Ancestor (LCA).
Return the distance between n1 and n2.
Input: root = [1,2,3,4,5,6,7], n1 = 4, n2 = 5
Output: 2
Explanation: The path 4 → 2 → 5 has 2 edges, so the distance is 2.
Input: root = [1,2,3,4,5,6,7], n1 = 4, n2 = 6
Output: 4
Explanation: The path 4 → 2 → 1 → 3 → 6 has 4 edges, so the distance is 4.
Input: root = [1,2,3], n1 = 2, n2 = 2
Output: 0
Explanation: A node has zero distance to itself.
- 1 = Number of nodes = 104
- -10? = Node.data = 10?
- Both n1 and n2 exist in the tree
See how the best solutions work
Approach, complexity and clean code in every language. Sign in to unlock the editorial.
Keep every attempt
Your submissions, results and runtime history live here. Sign in to start your streak.
10 5 15 2 7 12 20 2 20
4
8 4 10 2 6 9 12 2 6
2