Find the Distance Between Two Nodes in a Binary Tree - Algorithm & Examples

Problem Statement❯

Given a binary tree and two node values n1 and n2, find the number of edges in the shortest path between them. The distance between two nodes in a binary tree is defined as the number of edges in the path from one node to another.

If either node does not exist in the tree, return -1.

Examples❯

Input Tree	Node 1	Node 2	Distance	Description
[1, 2, 3, 4, 5, 6, 7]	4	5	2	LCA is 2. Distance = depth(4) + depth(5) - 2 × depth(2) = 2 + 2 - 2 = 2
[1, 2, 3, null, 4, null, 5]	4	5	4	LCA is 1. Path: 4 → 2 → 1 → 3 → 5 (4 steps)
[10, 5, 15, 3, 7, null, 18]	3	7	2	LCA is 5. Path: 3 → 5 → 7 = 2 steps
[1, 2, 3, 4, null, null, 5]	4	5	4	LCA is 1. Path: 4 → 2 → 1 → 3 → 5 = 4 steps
[1, 2, null, 3, null, 4]	3	4	2	LCA is 3. Distance from 3 to 4 is 1, from 3 to 3 is 0 → total = 1 + 1 = 2
[7]	7	7	0	Both nodes are the same → distance is 0

Solution❯

Understanding the Problem

We are given a binary tree and two distinct or identical node values. Our goal is to find the number of edges between these two nodes, also known as the distance between them.

To solve this, we rely on a fundamental concept called the Lowest Common Ancestor (LCA). The LCA of two nodes is the deepest node in the tree that has both target nodes as descendants (a node can be a descendant of itself).

Once the LCA is found, we calculate the distance from the LCA to each node and then sum them. This approach works whether the nodes are on different branches or one is the ancestor of the other.

Step-by-Step Solution with Example

Step 1: Represent the Binary Tree

Let’s consider the following binary tree:

      1
     /     2   3
   /   4   5

We’ll work with this structure to explain how to find the distance between two nodes, say 4 and 5.

Step 2: Understand the Path

We want the number of edges in the shortest path connecting the two nodes. The path from 4 to 5 goes like this:

4 → 2 → 5

This path has 2 edges. We can break this path using their LCA, which is node 2.

Step 3: Find the Lowest Common Ancestor (LCA)

We find the LCA of 4 and 5 by traversing the tree. Since both 4 and 5 are in the left subtree of 1 and share 2 as a common parent, the LCA is node 2.

Step 4: Find Distance from LCA to Each Node

Distance from LCA (2) to 4 is 1 edge.
Distance from LCA (2) to 5 is also 1 edge.

Step 5: Sum the Distances

Total distance between 4 and 5 = 1 (LCA to 4) + 1 (LCA to 5) = 2.

Edge Cases

Same Node

If we are asked for the distance between a node and itself, like 4 and 4, the distance is 0. No traversal is needed.

One Node is Ancestor of the Other

If one node is an ancestor of the other, the LCA will be the ancestor. For example, distance between 2 and 5 is 1, since 2 is the parent of 5.

Empty Tree

If the binary tree is null (empty), there’s nothing to search. Return -1 to indicate the nodes don’t exist.

One or Both Nodes Missing

If one or both nodes are not present in the tree, we should not attempt to find the distance. Instead, return -1 to signify invalid input.

Finally

Finding the distance between two nodes in a binary tree becomes intuitive once we understand the role of the Lowest Common Ancestor. Always remember to verify that both nodes exist in the tree before computing the distance. Carefully handling special cases like empty trees or same node queries ensures a robust and beginner-friendly implementation.

Algorithm Steps❯

Given a binary tree and two target node values.
Find the lowest common ancestor (LCA) of the two nodes.
Compute the distance from the LCA to the first node.
Compute the distance from the LCA to the second node.
The distance between the two nodes is the sum of these two distances.

Code

C++

Python

Java

Rust

Kotlin

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

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

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

TreeNode* lowestCommonAncestor(TreeNode* root, int n1, int n2) {
    if (!root || root->val == n1 || root->val == n2) return root;
    TreeNode* left = lowestCommonAncestor(root->left, n1, n2);
    TreeNode* right = lowestCommonAncestor(root->right, n1, n2);
    if (left && right) return root;
    return left ? left : right;
}

int distanceFromRoot(TreeNode* root, int target, int distance) {
    if (!root) return -1;
    if (root->val == target) return distance;
    int left = distanceFromRoot(root->left, target, distance + 1);
    if (left != -1) return left;
    return distanceFromRoot(root->right, target, distance + 1);
}

int distanceBetweenNodes(TreeNode* root, int n1, int n2) {
    TreeNode* lca = lowestCommonAncestor(root, n1, n2);
    int d1 = distanceFromRoot(lca, n1, 0);
    int d2 = distanceFromRoot(lca, n2, 0);
    return d1 + d2;
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("Distance between 4 and 5: %d\n", distanceBetweenNodes(root, 4, 5));
    return 0;
}

⬅ Previous TopicPrint All Paths in a Binary Tree with a Given Sum

Next Topic ⮕Find the kth Ancestor of a Node in a Binary Tree

Comments

Loading comments...