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.

Description Hints 2 Solution Video 11:47

1740. Find Distance in a Binary Tree

Medium74.3% acceptance2 companiesPremium elsewhere, free here

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, 10⁴].
0 <= Node.val <= 10⁹
All Node.val are unique.
p and q are values in the tree.

Asked at 2 companies

Apple Amazon

Topics

Hints open one at a time

Hint 1

Get the LCA of p and q.

Hint 2

The answer is the sum of distances between p-LCA and q-LCA

11:47

Still stuck?Read the written solution, or watch a walkthrough.

Open solution