ProgramGuru

Find the Distance Between Two Nodes in a Binary Tree

Problem and examples

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.

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

How it works

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.

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

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

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 = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    cout << "Distance between 4 and 5: " << distanceBetweenNodes(root, 4, 5) << endl;
    return 0;
}

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowestCommonAncestor(root, n1, n2):
    if not root or root.val == n1 or root.val == n2:
        return root
    left = lowestCommonAncestor(root.left, n1, n2)
    right = lowestCommonAncestor(root.right, n1, n2)
    if left and right:
        return root
    return left if left else right

def distanceFromRoot(root, target, distance):
    if not root:
        return -1
    if root.val == target:
        return distance
    left = distanceFromRoot(root.left, target, distance + 1)
    if left != -1:
        return left
    return distanceFromRoot(root.right, target, distance + 1)

def distanceBetweenNodes(root, n1, n2):
    lca = lowestCommonAncestor(root, n1, n2)
    d1 = distanceFromRoot(lca, n1, 0)
    d2 = distanceFromRoot(lca, n2, 0)
    return d1 + d2

if __name__ == '__main__':
    root = TreeNode(1)
    root.left = TreeNode(2, TreeNode(4), TreeNode(5))
    root.right = TreeNode(3)
    print(distanceBetweenNodes(root, 4, 5))  # Output: 2

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class DistanceBetweenNodes {
    public static TreeNode lowestCommonAncestor(TreeNode root, int n1, int n2) {
        if (root == null || root.val == n1 || root.val == n2)
            return root;
        TreeNode left = lowestCommonAncestor(root.left, n1, n2);
        TreeNode right = lowestCommonAncestor(root.right, n1, n2);
        if (left != null && right != null)
            return root;
        return left != null ? left : right;
    }

    public static int distanceFromRoot(TreeNode root, int target, int distance) {
        if (root == null)
            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);
    }

    public static 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;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        System.out.println(distanceBetweenNodes(root, 4, 5));
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function lowestCommonAncestor(root, n1, n2) {
    if (!root || root.val === n1 || root.val === n2) return root;
    const left = lowestCommonAncestor(root.left, n1, n2);
    const right = lowestCommonAncestor(root.right, n1, n2);
    if (left && right) return root;
    return left ? left : right;
}

function distanceFromRoot(root, target, distance) {
    if (!root) return -1;
    if (root.val === target) return distance;
    const left = distanceFromRoot(root.left, target, distance + 1);
    if (left !== -1) return left;
    return distanceFromRoot(root.right, target, distance + 1);
}

function distanceBetweenNodes(root, n1, n2) {
    const lca = lowestCommonAncestor(root, n1, n2);
    const d1 = distanceFromRoot(lca, n1, 0);
    const d2 = distanceFromRoot(lca, n2, 0);
    return d1 + d2;
}

const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5)),
    new TreeNode(3)
);
console.log(distanceBetweenNodes(root, 4, 5));

Go implementation

package main

import (
    "fmt"
)

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

func createNode(val int) *TreeNode {
    return &TreeNode{val: val}
}

func lowestCommonAncestor(root *TreeNode, n1, n2 int) *TreeNode {
    if root == nil || root.val == n1 || root.val == n2 {
        return root
    }
    left := lowestCommonAncestor(root.left, n1, n2)
    right := lowestCommonAncestor(root.right, n1, n2)
    if left != nil && right != nil {
        return root
    }
    if left != nil {
        return left
    }
    return right
}

func distanceFromRoot(root *TreeNode, target, dist int) int {
    if root == nil {
        return -1
    }
    if root.val == target {
        return dist
    }
    left := distanceFromRoot(root.left, target, dist+1)
    if left != -1 {
        return left
    }
    return distanceFromRoot(root.right, target, dist+1)
}

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

func main() {
    root := createNode(1)
    root.left = createNode(2)
    root.right = createNode(3)
    root.left.left = createNode(4)
    root.left.right = createNode(5)
    fmt.Println("Distance between 4 and 5:", distanceBetweenNodes(root, 4, 5))
}

Rust implementation

use std::rc::Rc;
use std::cell::RefCell;

type NodeRef = Rc<RefCell<TreeNode>>;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<NodeRef>,
    right: Option<NodeRef>,
}

impl TreeNode {
    fn new(val: i32) -> NodeRef {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn lowest_common_ancestor(root: Option<&NodeRef>, n1: i32, n2: i32) -> Option<NodeRef> {
    if let Some(node) = root {
        let node_ref = node.borrow();
        if node_ref.val == n1 || node_ref.val == n2 {
            return Some(Rc::clone(node));
        }
        let left = lowest_common_ancestor(node_ref.left.as_ref(), n1, n2);
        let right = lowest_common_ancestor(node_ref.right.as_ref(), n1, n2);
        if left.is_some() && right.is_some() {
            return Some(Rc::clone(node));
        }
        return left.or(right);
    }
    None
}

fn distance_from_root(root: Option<&NodeRef>, target: i32, distance: i32) -> i32 {
    if let Some(node) = root {
        let node_ref = node.borrow();
        if node_ref.val == target {
            return distance;
        }
        let left = distance_from_root(node_ref.left.as_ref(), target, distance + 1);
        if left != -1 {
            return left;
        }
        return distance_from_root(node_ref.right.as_ref(), target, distance + 1);
    }
    -1
}

fn distance_between_nodes(root: Option<&NodeRef>, n1: i32, n2: i32) -> i32 {
    if let Some(lca) = lowest_common_ancestor(root, n1, n2) {
        let d1 = distance_from_root(Some(&lca), n1, 0);
        let d2 = distance_from_root(Some(&lca), n2, 0);
        return d1 + d2;
    }
    -1
}

fn main() {
    let root = TreeNode::new(1);
    root.borrow_mut().left = Some(TreeNode::new(2));
    root.borrow_mut().right = Some(TreeNode::new(3));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().left = Some(TreeNode::new(4));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().right = Some(TreeNode::new(5));
    let dist = distance_between_nodes(Some(&root), 4, 5);
    println!("Distance between 4 and 5: {}", dist);
}

Kotlin implementation

class TreeNode(var val: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun lowestCommonAncestor(root: TreeNode?, n1: Int, n2: Int): TreeNode? {
    if (root == null || root.val == n1 || root.val == n2) return root
    val left = lowestCommonAncestor(root.left, n1, n2)
    val right = lowestCommonAncestor(root.right, n1, n2)
    if (left != null && right != null) return root
    return left ?: right
}

fun distanceFromRoot(root: TreeNode?, target: Int, distance: Int): Int {
    if (root == null) return -1
    if (root.val == target) return distance
    val left = distanceFromRoot(root.left, target, distance + 1)
    if (left != -1) return left
    return distanceFromRoot(root.right, target, distance + 1)
}

fun distanceBetweenNodes(root: TreeNode?, n1: Int, n2: Int): Int {
    val lca = lowestCommonAncestor(root, n1, n2)
    val d1 = distanceFromRoot(lca, n1, 0)
    val d2 = distanceFromRoot(lca, n2, 0)
    return d1 + d2
}

fun main() {
    val root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left!!.left = TreeNode(4)
    root.left!!.right = TreeNode(5)
    println("Distance between 4 and 5: ${distanceBetweenNodes(root, 4, 5)}")
}

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function lowestCommonAncestor(root: TreeNode | null, n1: number, n2: number): TreeNode | null {
    if (!root || root.val === n1 || root.val === n2) return root;
    const left = lowestCommonAncestor(root.left, n1, n2);
    const right = lowestCommonAncestor(root.right, n1, n2);
    if (left && right) return root;
    return left || right;
}

function distanceFromRoot(root: TreeNode | null, target: number, distance: number): number {
    if (!root) return -1;
    if (root.val === target) return distance;
    const left = distanceFromRoot(root.left, target, distance + 1);
    if (left !== -1) return left;
    return distanceFromRoot(root.right, target, distance + 1);
}

function distanceBetweenNodes(root: TreeNode, n1: number, n2: number): number {
    const lca = lowestCommonAncestor(root, n1, n2);
    const d1 = distanceFromRoot(lca, n1, 0);
    const d2 = distanceFromRoot(lca, n2, 0);
    return d1 + d2;
}

const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5)),
    new TreeNode(3)
);
console.log(`Distance between 4 and 5: ${distanceBetweenNodes(root, 4, 5)}`);