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).

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.