Skip to main content
Talentd

Find Distance in a Binary Tree - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableTreeDepth-First SearchBreadth-First Search6 min readAsked at: Amazon, Apple
Practice this problem

Problem Statement

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.val are unique.
  • p and q are 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

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Path to Root ComparisonO(n)O(n)When you want explicit root-to-node paths or a simple conceptual solution
Parent Map + BFSO(n)O(n)When treating the tree as an undirected graph simplifies traversal
Lowest Common Ancestor + DFSO(n)O(h)Best general solution for interviews and typical binary tree problems

Video Solution

FIND DISTANCE IN BINARY TREE | LEETCODE 1740 | PYTHON GRAPH BFS SOLUTION • Cracking FAANG • 2,070 views views

Watch 5 more video solutions →

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.

Ready to solve this problem?

Practice Find Distance in a Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Step-By-Step Directions From a Binary Tree Node to Another