Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
3.
Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation in C++
3.3.1.
Output
3.4.
Implementation in Java
3.4.1.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Frequently Asked Questions
4.1.
What is the difference between a binary tree and a binary search tree?
4.2.
What is unordered_map in C++ and the time complexity of various operations performed by it? 
4.3.
What are the various ways to navigate a binary tree?
4.4.
What is a binary tree post-order traversal?
4.5.
What are the applications of binary trees?
4.6.
What benefits and drawbacks do binary trees offer?
4.7.
What is the difference between a leaf node and a root node?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if all the Nodes in a Binary Tree having Common Values are at most D Distance Apart

Author Sahil Setia
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

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 preorderinorder, and postorder. A Binary tree is a widely asked data structure in programming contests and technical interviews.

Introduction Image

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:               

linked list initial image

Output

Yes

Explanation

The node values 7 and 8 are repeated.

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

Explanation umage linked list

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

Expalanation image linked list

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

  1. 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:
    1. If the ‘root’ is null, return.
    2. Increase the mapped item of the current key value of ‘root’ by 1.
    3. Call count_nodes() with ‘root -> left’ and ‘root -> right’.
       
  2. 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.
     
  3. If ‘root’ is null, return -1 indicating no such node exists with the key = val.
     
  4. 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.
     
  5. 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.
     
  6. If ‘dleft’ and ‘dright’, both are equal to -1, do the following:
    1. Check if the key of ‘root’ is equal to the ‘val’. If yes, return 1.
    2. Otherwise, return -1.
       
  7. 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.
    1. If the current node's key is equal to the val, update the dist variable to dist = max(dist, dright).
    2. Return 1 + dright.
       
  8. The other case where dleft != -1 and dright = -1 is symmetrical.
    1. 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).
       
  9. Now create the tree in the main() function. Create a unordered_map to contain the frequencies of unique key values.
     
  10. For all such key values with COUNT > 1, call the function maximum_distance() and check if dist > D.
     
  11. If the previous condition holds for any key, print No.
     
  12. Otherwise, print Yes.

Dry Run

Given input

Given input image

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)
Dry rune image 1
  • 2nd pass: root=7, dleft=?, dright=?
Dry rune image 2
  • 3rd pass: As the corresponding two nodes marked in the figure are leaf nodes and have a value of both will return 1.
Dry rune image 3
  • 4th pass: root=7, dleft=1, dright=1, dist=2
Dry rune image 4

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
Dry rune image 5
  • 6th pass: As the corresponding two nodes marked in the figure are leaf nodes and the left leaf node has a value of it will return 1 and dright will return -1.
Dry rune image 6

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.
Dry rune image 7
  • 8th pass: root=1, dleft=2, dright=2, dist=4(reaches its maximum for value 8)
Dry rune image 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 value 8 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

Output c++ image

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

Output Java image

Time Complexity

The time complexity of the above approach is O(N2), 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(N2).

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.

Check out this problem - Mirror A Binary Tree

Frequently Asked Questions

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.

Recommended Reading:

Do check out The Interview guide for Product Based Companies, as well as some of the popular interview problems, asked in top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, and 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.

Happy Coding!

Previous article
Smallest Subtree with all the Deepest Nodes
Next article
Find Maximum GCD Value from Root to Leaf in a Binary Tree
Live masterclass