Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Time and Space Complexity
4.
Frequently Asked Questions
4.1.
What is a Binary Tree?
4.2.
What is the LCA of a Binary Tree?
4.3.
What is the best-case time complexity for finding the distance between two nodes of a Binary Tree?
4.4.
What are the different possible Traversals for Binary Trees?
5.
Conclusion
Last Updated: Mar 27, 2024

Find Distance Between two Nodes of a Binary Tree

Author Raksha jain
1 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Binary Trees are popular Data Structures and have a wide range of applications throughout various fields. Binary Trees are also important when it comes to interviews with top tech companies. A mastery of Binary Trees could help us solve a lot of problems. In this article, we are going to take a look at one such problem.

Problem Statement

Given the root of the binary tree and the two nodes, we need to return the shortest distance between the two nodes.

Example: 

 

 

Let's consider the two given nodes as 7 and 9. The shortest distance between two nodes is three as-

7 -> 2 -> 5 -> 9. 

Hence, we would reach 9 from 7 (or vice versa) in 3 steps.

 

The approach to solving this problem is straightforward, i.e., via first finding the LCA(Least Common Ancestor) of the two given nodes and then calculating - (the distance between LCA and node1) + (the distance between LCA and node2).

This would be the shortest distance between two nodes of a Binary Tree.

Recommended: Try the Problem yourself before moving on to the solution.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

 

Output:

Form a tree: 3 9 20 15 7 
Enter node1  9

Enter node2  20

Distance between two nodes of a Binary Tree is: 2

 

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:

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!

Previous article
Find the Maximum Path Sum Between Two Leaves of A Binary Tree
Next article
Mirror Tree from the given Binary Tree
Live masterclass