Find Distance Between two Nodes of a Binary Tree

Approach

STEP 1: Calculate LCA(Least Common Ancestor)

The lowest common ancestor(LCA) between two nodes n1 and n2 is defined as the lowest node in Binary Tree with both n1 and n2 as descendants (where we allow a node to be a descendant of itself). 

To calculate the LCA of nodes 7 and 9, we first call a recursive function passing (the root of Binary Tree, Node1 i.e.7, Node2, i.e., 9).

• We first check in our base case if (root == null), stating we have a null tree or have reached a null node. If this is the case, we return null.
• Otherwise, we check if the root (or current node) equals Node1 or Node2. If it is so, we return the root.
• Otherwise, we further explore in both the left and the right direction. If both the directions return some non-null node, this means our LCA would be our current node(i.e., root). So we return the root node. 
• Otherwise, we return the not null node we received from either of the sides or a null node if we received a null node from both the left and right subtrees denoting that they do not contain any of the nodes n1 and n2.  

STEP 2: Find the distance of Node 1 and Node2 from the LCA. 

So, we again traverse the tree until we find the level from our LCA node, where our "to-found node" is located.

Finally, we sum both the distances (distance from LCA to Node1 and LCA to Node2) and return our answer(the shortest distance between two nodes of a Binary Tree).

Implementation-

Let’s have a look at its implementation in Java

import java.util.*;
import java.lang.*;
import java.io.*;
 
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
 
class Solution {
    public static void main (String[] args) throws java.lang.Exception
{
  Scanner s = new Scanner(System.in);
        System.out.println("Form a tree: ");
        TreeNode root = new TreeNode(s.nextInt());
        root.left = new TreeNode(s.nextInt());
        root.right = new TreeNode(s.nextInt());
        root.right.left = new TreeNode(s.nextInt());
        root.right.right = new TreeNode(s.nextInt());
 
        System.out.println("Enter node1");
        TreeNode node1 = new TreeNode(s.nextInt());
        System.out.println("Enter node2");
        TreeNode node2 = new TreeNode(s.nextInt());
        
        TreeNode lca = LCA(root, node1, node2);
        
        int sum = distance(root, node1,0) + distance(root, node2, 0);
        System.out.println("Distance between two nodes of a Binary Tree is: " + sum);
}

public static TreeNode LCA(TreeNode root, TreeNode node1, TreeNode node2){
    if (root == null) return null;
    
    // Given node found
    if (root.val == node1.val || root.val == node2.val) 
               return root;
    
    TreeNode n1 = LCA(root.left, node1, node2);
    TreeNode n2 = LCA(root.right, node1, node2);
    
    // if both nodes found => LCA is our root
    if (n1 != null && n2 != null) return root;
    if (n1 != null) return n1;
    return n2;
}

public static int distance(TreeNode root, TreeNode node, int level){
    
    // NULL Node Reached
    if (root == null) return -1;
    
    // Given node found
    if (root.val == node.val) return level;
    
    // Search on left side of Tree
    int left = distance(root.left, node, level + 1);
    if (left != -1) return left;
    
    // Search on right side of Tree
    return distance(root.right, node, level + 1);
}
}

You can also try this code with Online Java Compiler

Run Code

Output:

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary tree as in the worst case we are traversing all the nodes of the Binary tree.

Space Complexity: O(1) as no extra space is being used.

Frequently Asked Questions

What is a Binary Tree?

A generic tree with at most two child nodes for each parent node is known as a Binary Tree. An empty tree is also considered a valid Binary Tree.

What is the LCA of a Binary Tree?

The lowest common ancestor(LCA) between two nodes n1 and n2 is defined as the lowest node in Binary Tree with both n1 and n2 as descendants (where we allow a node to be a descendant of itself).   

What is the best-case time complexity for finding the distance between two nodes of a Binary Tree?

The best-case time complexity for finding the distance between two nodes of a Binary Tree is O(1), i.e. when only a single or no node is present in the Binary Tree.

What are the different possible Traversals for Binary Trees?

The different possible traversals of Binary Tree are level-order traversal, Diagonal traversal, etc.

Conclusion

In this blog, we learned about the distance between two nodes of a Binary Tree.
 

• It could be calculated by finding the LCA(Least Common Ancestor) of the two given nodes and then summing - (the distance between LCA and node1) + (the distance between LCA and node2). 
• The time complexity is O(n) where n = number of nodes in a Binary Tree as we need to traverse all the nodes of the Binary Tree in the worst case.

Recommended Reading:

• Boundary Traveral of Binary Tree
• Diagonal Traversal of Binary Tree
• Level Order Traversal of Binary Tree
• Traversal in Binary Tree
• Sum of Distance of Nodes From a Given Node
• Find the Sum of Nodes on the Longest Path From Root to Leaf Node
• Diamond Tree
• The Maximum Level Sum in Binary Tree
• Difference Between Binary Tree and Binary Search Tree
• Find The Maximum Path Sum Between Two Leaves of a Binary Tree
• Sum of Leaf Node at Each Horizontal Level in Binary Tree

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!