Hey Ninjas! In this blog, we will discuss a problem based on Binary trees. A Binary Tree is a data structure where data is stored in a node, and each node has either two child nodes, one child node, or no child node. The three primary traversal techniques are preorder, inorder, and postorder. A Binary tree is a widely asked data structure in programming contests and technical interviews.

This blog will discuss the approach to check if all the nodes in a binary tree having common values are at most D distance apart. We will modify the approach to this problem to find the solution to our problem. This blog also discusses the post-order traversal of a tree used to find the shortest distance.

Problem Statement

You are given a binary tree and an integer ‘D’. Your task is to check if two nodes having the same value are more than a ‘D’ distance apart. If there exist a pair of nodes satisfying the criteria, output ‘No’ else print ‘Yes’.

Input

D = 4

Binary Tree:

Output

Yes

Explanation

The node values 7 and 8 are repeated.

The dist. between the two nodes having a value of 7 is two.

The maximum distance between any two nodes with a value of 8 is four.

As a result, none of the distances exceed four.

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

As you can observe, we only need to consider those key values that occur at least twice in the given binary tree. We can find all such key values using a hash map by mapping them to their count. If the count is greater than one, Such a key value is repeated. Take one such key, 'K'.

Do the post-order traversal of the given binary tree and find the deepest node in each of the left and right subtrees with the value K. Assuming that both left and right subtrees contain a node with key K, find the distance between them by summing up the depths of the nodes in their respective subtrees. If this distance exceeds the limit 'D', print No. Otherwise, if no such pair exists, print Yes.

Algorithm

Create a recursive function count_nodes(Node* root) to map all the unique key values to the number of nodes with those keys as follows:

If the ‘root’ is null, return.

Increase the mapped item of the current key value of ‘root’ by 1.

Call count_nodes() with ‘root -> left’ and ‘root -> right’.

Create a recursive function maximum_distance(Node* root, int val) that computes the longest distance between two nodes with the same key equal to the second parameter.

If ‘root’ is null, return -1 indicating no such node exists with the key = val.

Initialize a variable ‘dleft’ with maximum_distance(root->left, val) that will contain the depth of such a node in the left subtree of the current node.

Initialize a variable, ‘dright’ with maximum_distance(root->right, val) that will contain the depth of such a node in the right subtree of the current node.

If ‘dleft’ and ‘dright’, both are equal to -1, do the following:

Check if the key of ‘root’ is equal to the ‘val’. If yes, return 1.

Otherwise, return -1.

If ‘dleft’ is -1 and ‘dright’ is not equal to -1, there is a node with key = val in the right subtree but not in the left subtree.

If the current node's key is equal to the val, update the dist variable to dist = max(dist, dright).

Return 1 + dright.

The other case where dleft != -1 and dright = -1 is symmetrical.

However, if both dleft and dright are not -1, this implies there exist nodes with the key = val in both the subtrees. Hence, update the dist variable to dist = max(dist, dleft + dright).

Now create the tree in the main() function. Create a unordered_map to contain the frequencies of unique key values.

For all such key values with COUNT > 1, call the function maximum_distance() and check if dist > D.

If the previous condition holds for any key, print No.

Otherwise, print Yes.

Dry Run

Given input

Let’s see a dry run of the Maximum_Distance() function with a sample value ‘8’, i.e., we want to calculate the maximum distance between any two nodes with value ‘8’.

1st pass: root=1, dleft=?, dright=? Note: (? means yet to be calculated)

2nd pass: root=7, dleft=?, dright=?

3rd pass: As the corresponding two nodes marked in the figure are leaf nodes and have a value of 8 both will return 1.

4th pass: root=7, dleft=1, dright=1, dist=2

Explanation: Here, when the root is 7 we obtain dleft=1 and dright=1. We observe that dleft>0 and dright>0 hence both the left and right subtree contains a node that has value 8 so the condition ‘dist=max(dist, dleft + dright)’ is evaluated and dist is getting updated to the value of 1+1=2.

5th pass: As previously when the root had a value equal to 1 we first called the recursion for the left subtree and then for the right subtree. Hence, after the left subtree, the right subtree of root=1 will get evaluated. So root=7, dleft=?, dright=?, dist=2

6th pass: As the corresponding two nodes marked in the figure are leaf nodes and the left leaf node has a value of 8 it will return 1 and dright will return -1.

Here, -1 means there is no node in that subtree.

7th pass: root=7, dleft=1, dright=-1, dist=2

Explanation: Here, the value for the left subtree ‘dleft’ is equal to 1 and the value for the right subtree ‘dright’ is equal to -1. Hence the condition where ‘dright=-1’ will get evaluated and our dist will maximise itself with the condition ‘dist=max(dist,dleft)’. So here dleft=1 hence dist=max(dist,1) so our dist will still remain 2 as its previous maximum value.

8th pass: root=1, dleft=2, dright=2, dist=4(reaches its maximum for value 8)

Explanation: Here, when the root is 1 we obtain dleft=2 and dright=2. We observe that dleft>0 and dright>0 hence both the left and right subtree contains a node that has value 8 so the condition ‘dist=max(dist, dleft + dright)’ is evaluated and dist is getting updated to the value of ‘2+2=4’ from its previous value of 2.

Hence, for value8 the maximum distance between any two nodes is 4.

We will perform this for each value greater than one and calculate the overall maximum and compare it with the given value D. As a result, the maximum distance is at most four. So, the output for the sample input is ‘Yes’.

Implementation in C++

// Importing bits/stdc++.h library including all libraries
#include<bits/stdc++.h>
using namespace std;
// Class to represent a Binary Tree node.
class Node{
public:
int key;
Node* left, *right;
// Parametrized constructor
Node(int val){
this->key = val;
this->left = NULL;
this->right = NULL;
}
};
int dist = INT_MIN;
// Function to calculate maximum distance between nodes of value 'val'
int maximum_distance(Node* root, int val){
if(root == NULL) return -1;
// Calling for the left child
int dleft = maximum_distance(root->left, val);
// Calling for the right child
int dright = maximum_distance(root->right, val);
if(dleft == -1 && dright == -1) {
if(root->key == val){
// Count the edge that connects this node to its parent.
return 1;
}
return -1;
}
// If there is no node with KEY == VAL in the left subtree.
if(dleft == -1){
if(root->key == val){
/*
The two nodes are the current node
and the node in the right subtree.
*/
dist = max(dist, dright);
}
/*
Add one to take into this edge that
connects the current node to its parent.
*/
return dright + 1;
}
// If there is no node with KEY == VAL in the right subtree.
if(dright == -1){
if(root->key == val){
/*
The two nodes are the current node
and the node in the left subtree.
*/
dist = max(dist, dleft);
}
/*
Add one to take into this edge that
connects the current node to its parent.
*/
return dleft + 1;
}
// If there is a node on both sides, update the maximum distance.
dist = max(dist, dleft + dright);
// Return the node with max depth.
return 1 + max(dleft, dright);
}
// Function to count the number of nodes of all unique keys.
void count_nodes(unordered_map<int,int>& freq, Node* root){
if(root == NULL) return;
// Increase the count for the current node.
freq[root->key]++;
// Go for the left child.
count_nodes(freq, root->left);
// Go for the right child
count_nodes(freq, root->right);
}
bool is_condition_satisfied(int dis, Node* root){
// Hashmap to store the frequency of tree Nodes Values.
unordered_map<int,int> frequency;
// Function for storing
count_nodes(frequency, root);
// Boolean to return the result.
bool condition_satisfied = true;
for(auto &it:frequency){
if(it.second > 1){
// Minimum distance is one.
dist = 1;
/*
Compute the maximum distance
between any two nodes with the
same key = it->second.
*/
maximum_distance(root, it.first);
/*
distance > d then the condition is false we have to return
*/
if(dist > dis){
condition_satisfied = false;
break;
}
}
}
// Return the result.
return condition_satisfied;
}
int main(){
// Value of variable D
int dis = 4;
/*
Create the tree.
Initialize the root of the Tree
*/
Node* root = new Node(1);
root->left = new Node(7);
root->right = new Node(7);
root->left->left = new Node(8);
root->left->right = new Node(8);
root->right->left = new Node(8);
root->right->right = new Node(5);
bool condition_satisfied = is_condition_satisfied(dis, root);
// If no such nodes exist print Yes.
if(condition_satisfied){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
return 0;
}

Output

Implementation in Java

import java.util.*;
public class MyClass {
static int dist=-1000000000;
// Structure of a Binary Tree node
static class Node{
int key;
Node left, right;
};
// Function to create a new node
static Node newNode(int key){
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
/*
Function to store the frequency of
Tree Nodes in the HashMap
*/
static void count_nodes(HashMap<Integer,Integer> freq,Node root){
if (root == null)
return;
// Inserting current node value in HashMap
if(freq.containsKey(root.key))
freq.put(root.key, freq.get(root.key) + 1);
else
freq.put(root.key, 1);
// Calling function for left node
count_nodes(freq, root.left);
// Calling function for the right node
count_nodes(freq, root.right);
}
/*
Function that returns the maximum distance
between the nodes that have the value 'value'
*/
static int maximum_distance(Node root, int val){
if (root == null){
return -1;
}
// Computing for left Tree
int dleft = maximum_distance(root.left, val);
// Computing for the right Tree
int dright = maximum_distance(root.right, val);
/*
If the corresponding left and right subtree
both didn't have a node whose value is equal to val
*/
if (dleft == -1 && dright == -1){
/*
If the value of the current
node is equal to the val
*/
if (root.key == val){
// Count the edge that connects this node to its parent.
return 1;
}
else
return -1;
}
// If there is no node with KEY == VAL in the left subtree.
if (dleft == -1){
if(root.key==val){
// The two nodes are the current node and the node in the right subtree.
dist=Math.max(dist,dright);
}
/*
Add one to take into this edge that
connects the current node to its parent.
*/
return dright + 1;
}
// If there is no node with KEY == VAL in the right subtree.
if (dright == -1){
if(root.key==val){
// The two nodes are the current node and the node in the left subtree.
dist=Math.max(dist,dleft);
}
// Add one to take into this edge that connects the current node to its parent.
return dleft + 1;
}
else{
// If there is a node on both sides, update the maximum distance.
dist=Math.max(dist,dleft+dright);
// Return the node with max depth.
return 1 + Math.max(dleft, dright);
}
}
/*
Function to call for each value and
check for the longest distance for that value
*/
static boolean is_condition_satisfied(Node root, int dis){
// Hashmap to store the frequency of tree Nodes Values.
HashMap<Integer,Integer> freq = new HashMap<Integer,Integer>();
// Function for storing Tree Nodes frequency
count_nodes(freq, root);
boolean condition_satisfied = true;
// Iterating over all values
for(Map.Entry<Integer,Integer> it : freq.entrySet())
{
if (it.getValue() > 1){
// Minimum value
dist=1;
// Calling longest distance function for current value
int p=maximum_distance(root, it.getKey());
// If the overall value of dist exceeds dis
if (dist > dis){
condition_satisfied = false;
break;
}
}
}
return condition_satisfied;
}
// Driver Code for running the main function
public static void main(String[] args){
// Creating the Tree
// Initializing the root
Node root = newNode(1);
root.left = newNode(7);
root.right = newNode(7);
root.left.left = newNode(8);
root.left.right = newNode(8);
root.right.right = newNode(5);
root.right.left = newNode(8);
// Value of variabel 'D'
int dis = 4;
boolean condition_satisfied = is_condition_satisfied(root, dis);
// If no such nodes exist print Yes.
if(condition_satisfied){
System.out.println("Yes");
}
else{
System.out.println("No");
}
}
}

Output

Time Complexity

The time complexity of the above approach is O(N^{2}), where ‘N’ is the total number of nodes in the tree.

The post-order traversal to find the distance between two nodes is O(N), and there can be an O(N) number of nodes with the same key. Hence the worst-case time complexity can be O(N^{2}).

Space Complexity

The space complexity of the above approach is O(H), where ‘H’ is the height of the tree as the recursion stack can be O(H) deep at any moment.

What is the difference between a binary tree and a binary search tree?

A binary search tree is a specific type of binary tree where the left child node has a value less than the parent node, and the right child node has a value greater than the parent node. This allows for efficient searching and insertion of elements in the tree.

What is unordered_map in C++ and the time complexity of various operations performed by it?

Unordered maps are containers that store elements as key-value pairs. The ‘key’ is used to uniquely identify a ‘value’ for each key-value pair.

The average time complexity of operations like insert, search and delete with unordered_map is O(1).

What are the various ways to navigate a binary tree?

In-order, pre-order, and post-order are the three typical ways to navigate through a binary tree in depth-first order.

What is a binary tree post-order traversal?

One of the traversing methods used to visit the node in the tree is postorder traversal. It adheres to the LRN principle (Left-right-node). To determine a tree's postfix expression, postorder traversal is employed.

What are the applications of binary trees?

Binary Trees are used for implementing priority queues and performing encoding and decoding operations.

What benefits and drawbacks do binary trees offer?

A binary tree's searching operation is quick, and they're also simple to use and comprehend.

Many pointers in binary tree traversals are null and so worthless, and deletions in binary trees are difficult.

What is the difference between a leaf node and a root node?

In a binary tree, a leaf node is any node that does not possess any child node. In contrast, a root node is the first node on a binary tree, which all other nodes in the sequence stem from.

Conclusion

In this blog, we discussed a problem based on binary trees and used the concept of the longest distance between two nodes having the same value in a Binary Tree. We found this using the concept of post-order traversal of the tree. We also discussed the hashing concept to find the number of nodes with the same key. We learned to modify the post-order traversal of the binary tree to find the longest distance. It is usual to modify well-known algorithms to serve our purpose.