Find Distance in a Binary Tree - Practice Coding Problems

Find Distance in a Binary Tree - Problem

Given the root of a binary tree and two integers p and q, return the distance between the nodes of value p and q in the tree.

The distance between two nodes is the number of edges on the path from one to the other.

Note: You can assume that both values p and q exist in the tree and all node values are unique.

Input & Output

Example 1 — Basic Distance

$ Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

› Output: 3

💡 Note: The path from node 5 to node 1 is: 5 → 3 → 1, which has 2 edges. So the distance is 2.

Example 2 — Same Subtree

$ Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

› Output: 3

💡 Note: The path from node 5 to node 4 is: 5 → 2 → 4, which has 2 edges. So the distance is 2.

Example 3 — Adjacent Nodes

$ Input: root = [1,2,3], p = 2, q = 3

› Output: 2

💡 Note: The path from node 2 to node 3 is: 2 → 1 → 3, which has 2 edges. So the distance is 2.

Constraints

The number of nodes in the tree is in the range [1, 10⁴]
0 ≤ Node.val ≤ 10⁴
All Node.val are unique
p ≠ q
p and q exist in the tree

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with two target nodes p and q

Find LCA

Locate the lowest common ancestor of both nodes

Calculate Distance

Sum distances from LCA to each target node

Key Takeaway

🎯 Key Insight: The shortest path between any two nodes always goes through their lowest common ancestor

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The key insight is that the shortest path between two nodes in a binary tree always passes through their lowest common ancestor (LCA). The optimal approach uses DFS to find the LCA first, then calculates distances from LCA to both target nodes. Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Path Finding	O(n)	O(h)	Find paths from root to both nodes, then calculate distance from path difference
DFS with LCA Finding	O(n)	O(h)	Use DFS to find lowest common ancestor, then calculate distances from LCA to both nodes

Brute Force Path Finding — Algorithm Steps

Find complete path from root to node p
Find complete path from root to node q
Compare paths to find lowest common ancestor
Calculate distance as (path_p - lca) + (path_q - lca)

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Path to P

Traverse tree to find complete path from root to node p

Find Path to Q

Traverse tree to find complete path from root to node q

Calculate Distance

Compare paths to find LCA and sum distances

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int findPath(struct TreeNode* node, int target, int* path, int* pathLen) {
    if (!node) return 0;
    path[*pathLen] = node->val;
    (*pathLen)++;
    if (node->val == target) return 1;
    if (findPath(node->left, target, path, pathLen) || findPath(node->right, target, path, pathLen)) {
        return 1;
    }
    (*pathLen)--;
    return 0;
}

int solution(struct TreeNode* root, int p, int q) {
    int pathP[1000], pathQ[1000];
    int pathPLen = 0, pathQLen = 0;
    findPath(root, p, pathP, &pathPLen);
    findPath(root, q, pathQ, &pathQLen);
    
    int i = 0;
    while (i < pathPLen && i < pathQLen && pathP[i] == pathQ[i]) {
        i++;
    }
    
    return pathPLen - i + pathQLen - i;
}

int main() {
    // Simplified for demonstration - assumes tree structure is built
    struct TreeNode* root = createNode(3);
    root->left = createNode(5);
    root->right = createNode(1);
    root->left->left = createNode(6);
    root->left->right = createNode(2);
    root->right->left = createNode(0);
    root->right->right = createNode(8);
    root->left->right->left = createNode(7);
    root->left->right->right = createNode(4);
    
    int p = 5, q = 1;
    printf("%d\n", solution(root, p, q));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Three tree traversals in worst case - one for each path and one for comparison

✓ Linear Growth

Space Complexity

O(h)

Two arrays to store paths from root to target nodes, each of height h

✓ Linear Space

31.2K Views

Medium Frequency

~25 min Avg. Time

875 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Path Finding — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler