Find Distance in a Binary Tree solution and explanation
5 more videos on this problem
FIND DISTANCE IN BINARY TREE | LEETCODE 1740 | PYTHON GRAPH BFS SOLUTIONCracking FAANG · 11:47 · 2K views
1740 Find Distance in a Binary Tree - Python Programming Interview Facebook Amazon Netflix GoogleLearn with Amine · 5:18 · 402 views
1740. Find Distance in a Binary Tree - Week 3/5 Leetcode July ChallengeProgramming Live with Larry · 14:05 · 273 views
Leetcode 1740. Find Distance in a Binary Tree (LCA or Graph)LetsCode · 12:16 · 73 views
Leetcode 1740 Find Distance in a Binary TreeDev_God · 9:18 · 71 views
LeetCode 1740: Find Distance in a Binary TreeAlitaCode · 31:33 · 12 views
The problem
Given the root of a binary tree and two integers p and q, return the distance between the nodes of value p and value q in the tree.
The distance between two nodes is the number of edges on the path from one to the other.
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 0 Output: 3 Explanation: There are 3 edges between 5 and 0: 5-3-1-0.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 7 Output: 2 Explanation: There are 2 edges between 5 and 7: 5-2-7.
Example 3:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 5 Output: 0 Explanation: The distance between a node and itself is 0.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. 0 <= Node.val <= 109- All
Node.valare unique. pandqare values in the tree.
Approach overview
Problem Overview: Given the root of a binary tree and two node values p and q, compute the number of edges in the shortest path between them. The distance is the count of edges you must traverse to move from node p to node q.
Approach 1: Path to Root Comparison (O(n) time, O(n) space)
One straightforward strategy stores the path from the root to each target node. Use a Depth-First Search to build two arrays: the path to p and the path to q. Iterate from the beginning of both paths until the nodes diverge. The last common node is the Lowest Common Ancestor (LCA). The distance becomes (len(path_p) - i) + (len(path_q) - i), where i is the divergence index. This approach is easy to reason about and useful when you want explicit root-to-node paths.
Approach 2: Convert Tree to Graph + BFS (O(n) time, O(n) space)
A binary tree does not normally allow upward traversal. Build a parent map using a DFS traversal and store each node's parent in a hash table. After that, treat the tree like an undirected graph. Start a Breadth-First Search from node p. At every step, explore the left child, right child, and parent while tracking visited nodes. BFS guarantees the first time you reach q is through the shortest path. The BFS level count directly represents the distance in edges.
Approach 3: Lowest Common Ancestor + Depth Search (O(n) time, O(h) space)
The most common interview solution finds the Lowest Common Ancestor of nodes p and q in a binary tree. First run a DFS to locate the LCA. Once the LCA is known, run another DFS from the LCA to compute the depth to p and the depth to q. The total distance is the sum of those two depths. This works because every path between two nodes must pass through their LCA. The recursion stack only stores nodes along the current branch, so space depends on tree height h.
Recommended for interviews: The LCA + depth search approach is the one interviewers expect. It shows you understand tree structure and avoids unnecessary parent maps or extra arrays. The BFS-with-parent-map solution is also valid and often easier to implement quickly. Mentioning the path-comparison method first demonstrates your reasoning from brute force to optimal design.
Solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:
def lca(root, p, q):
if root is None or root.val in [p, q]:
return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
if left is None:
return right
if right is None:
return left
return root
def dfs(root, v):
if root is None:
return -1
if root.val == v:
return 0
left, right = dfs(root.left, v), dfs(root.right, v)
if left == right == -1:
return -1
return 1 + max(left, right)
g = lca(root, p, q)
return dfs(g, p) + dfs(g, q)/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int findDistance(TreeNode root, int p, int q) {
TreeNode g = lca(root, p, q);
return dfs(g, p) + dfs(g, q);
}
private int dfs(TreeNode root, int v) {
if (root == null) {
return -1;
}
if (root.val == v) {
return 0;
}
int left = dfs(root.left, v);
int right = dfs(root.right, v);
if (left == -1 && right == -1) {
return -1;
}
return 1 + Math.max(left, right);
}
private TreeNode lca(TreeNode root, int p, int q) {
if (root == null || root.val == p || root.val == q) {
return root;
}
TreeNode left = lca(root.left, p, q);
TreeNode right = lca(root.right, p, q);
if (left == null) {
return right;
}
if (right == null) {
return left;
}
return root;
}
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int findDistance(TreeNode* root, int p, int q) {
TreeNode* g = lca(root, p, q);
return dfs(g, p) + dfs(g, q);
}
TreeNode* lca(TreeNode* root, int p, int q) {
if (!root || root->val == p || root->val == q) return root;
TreeNode* left = lca(root->left, p, q);
TreeNode* right = lca(root->right, p, q);
if (!left) return right;
if (!right) return left;
return root;
}
int dfs(TreeNode* root, int v) {
if (!root) return -1;
if (root->val == v) return 0;
int left = dfs(root->left, v);
int right = dfs(root->right, v);
if (left == -1 && right == -1) return -1;
return 1 + max(left, right);
}
};/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findDistance(root *TreeNode, p int, q int) int {
var lca func(root *TreeNode, p int, q int) *TreeNode
lca = func(root *TreeNode, p int, q int) *TreeNode {
if root == nil || root.Val == p || root.Val == q {
return root
}
left, right := lca(root.Left, p, q), lca(root.Right, p, q)
if left == nil {
return right
}
if right == nil {
return left
}
return root
}
var dfs func(root *TreeNode, v int) int
dfs = func(root *TreeNode, v int) int {
if root == nil {
return -1
}
if root.Val == v {
return 0
}
left, right := dfs(root.Left, v), dfs(root.Right, v)
if left == -1 && right == -1 {
return -1
}
return 1 + max(left, right)
}
g := lca(root, p, q)
return dfs(g, p) + dfs(g, q)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Path to Root Comparison | O(n) | O(n) | When you want explicit root-to-node paths or a simple conceptual solution |
| Parent Map + BFS | O(n) | O(n) | When treating the tree as an undirected graph simplifies traversal |
| Lowest Common Ancestor + DFS | O(n) | O(h) | Best general solution for interviews and typical binary tree problems |
Frequently asked questions
Is Find Distance in a Binary Tree easy or hard?
Find Distance in a Binary Tree is generally rated Medium difficulty. The challenge comes from recognizing that the shortest path between two nodes passes through their Lowest Common Ancestor and structuring the traversal efficiently.
Find Distance in a Binary Tree Python/Java solution
Most implementations follow the LCA approach. A DFS identifies the lowest common ancestor, and another DFS measures depth to p and q. The same logic works across Python, Java, C++, and Go with only minor syntax differences.
How to solve Find Distance in a Binary Tree in O(n)?
Traverse the tree with DFS to find the Lowest Common Ancestor of nodes p and q. After identifying the LCA, run DFS again to compute the distance from the LCA to each target node. Since each traversal touches at most n nodes, the overall complexity remains O(n).
What is the best approach for Find Distance in a Binary Tree?
The most efficient and commonly expected approach uses the Lowest Common Ancestor (LCA). First find the LCA of nodes p and q using DFS, then compute the depth from the LCA to each node. The distance equals the sum of those depths. This runs in O(n) time and O(h) space where h is the tree height.
Is Find Distance in a Binary Tree asked at Google/Amazon/Meta?
Binary tree distance and Lowest Common Ancestor variations frequently appear in interviews at companies like Amazon, Google, and Meta. The problem tests tree traversal, recursion, and understanding of ancestor relationships within a tree.
What data structure is used in Find Distance in a Binary Tree?
The core data structure is a binary tree. Typical solutions rely on Depth-First Search recursion, sometimes combined with a hash map to store parent references, or Breadth-First Search when treating the tree as an undirected graph.
What is the time complexity of Find Distance in a Binary Tree?
The optimal solution runs in O(n) time because every node may be visited once while searching for the LCA and the target nodes. Space complexity is O(h) for recursion stack depth in a balanced tree, or O(n) in the worst case of a skewed tree.