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

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

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

You can also try this code with Online C++ Compiler

Run Code

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

You can also try this code with Online Java Compiler

Run Code

Output

Time Complexity

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

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:

• Create a Balanced Binary Tree using leaf Nodes of a Binary Tree without using Extra Space
• Construct a Binary Tree from a given Preorder and Inorder Traversal
• Construct a Complete Binary Tree from its Linked List Representation
• Diagonal Traversal of Binary Tree (Recursive and Iterative)
• Find the Minimum and Maximum Number of Nodes Between Critical Points
• Level Order Traversal in Spiral Form
   

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!