Given a Binary Tree and an integer D, the task is to check if the distance between all pairs of the same node values in the Tree is? D or not. If found to be true, then print Yes. Otherwise, print No.
Examples:
Input: D = 7
1 / \ 2 3 / \ / \ 4 3 4 4Output: Yes
Explanation:
The repeated value of nodes are 3 and 4.
The distance between the two nodes valued 3, is 3.
The maximum distance between any pair of nodes valued 4 is 4.
Therefore, none of the distances exceed 7Input: D = 1
3 / \ 3 3 \ 3Output: No
Approach:
The idea is to observe that the problem is similar to finding the distance between two nodes of a tree. But there can be multiple pairs of nodes for which we have to find the distance. Follow the steps below:
- Perform the Post Order Traversal of the given tree and find the distance between the repeated pairs of nodes.
- Find the nodes that are repeated in the tree using unordered_map.
- For each repeated node of a particular value, find the maximum possible distance between any pair.
- If that distance is > D, print “No”.
- If no such node value is found having a pair containing that value, exceeding D, then print “Yes”.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Structure of a Tree node struct Node { int key; struct Node *left, *right; }; // Function to create a new node Node* newNode( int key) { Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp); } // Function to count the frequency of // node value present in the tree void frequencyCounts(unordered_map< int , int >& map, Node* root) { if (root == NULL) return ; map[root->key]++; frequencyCounts(map, root->left); frequencyCounts(map, root->right); } // Function that returns the max distance // between the nodes that have the same key int computeDistance(Node* root, int value) { if (root == NULL) { return -1; } int left = computeDistance(root->left, value); int right = computeDistance(root->right, value); // If right and left subtree did not // have node whose key is value if (left == -1 && right == -1) { // Check if the current node // is equal to value if (root->key == value) { return 1; } else return -1; } // If the left subtree has no node // whose key is equal to value if (left == -1) { return right + 1; } // If the right subtree has no node // whose key is equal to value if (right == -1) { return left + 1; } else { return 1 + max(left, right); } return -1; } // Function that finds if the distance // between any same nodes is at most K void solve(Node* root, int dist) { // Create the map to look // for same value of nodes unordered_map< int , int > map; // Counting the frequency of nodes frequencyCounts(map, root); int flag = 0; for ( auto it = map.begin(); it != map.end(); it++) { if (it->second > 1) { // If the returned value of // distance is exceeds dist int result = computeDistance(root, it->first); if (result > dist || result == -1) { flag = 1; break ; } } } // Print the result flag == 0 ? cout << "Yes\n" : cout << "No\n" ; } // Driver Code int main() { Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(3); root->right->right = newNode(4); root->right->left = newNode(4); int dist = 7; solve(root, dist); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Structure of a 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 count the frequency of // node value present in the tree static void frequencyCounts(HashMap<Integer, Integer> map, Node root) { if (root == null ) return ; if (map.containsKey(root.key)) map.put(root.key, map.get(root.key) + 1 ); else map.put(root.key, 1 ); frequencyCounts(map, root.left); frequencyCounts(map, root.right); } // Function that returns the max distance // between the nodes that have the same key static int computeDistance(Node root, int value) { if (root == null ) { return - 1 ; } int left = computeDistance(root.left, value); int right = computeDistance(root.right, value); // If right and left subtree did not // have node whose key is value if (left == - 1 && right == - 1 ) { // Check if the current node // is equal to value if (root.key == value) { return 1 ; } else return - 1 ; } // If the left subtree has no node // whose key is equal to value if (left == - 1 ) { return right + 1 ; } // If the right subtree has no node // whose key is equal to value if (right == - 1 ) { return left + 1 ; } else { return 1 + Math.max(left, right); } } // Function that finds if the distance // between any same nodes is at most K static void solve(Node root, int dist) { // Create the map to look // for same value of nodes HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); // Counting the frequency of nodes frequencyCounts(map, root); int flag = 0 ; for (Map.Entry<Integer, Integer> it : map.entrySet()) { if (it.getValue() > 1 ) { // If the returned value of // distance is exceeds dist int result = computeDistance( root, it.getKey()); if (result > dist || result == - 1 ) { flag = 1 ; break ; } } } // Print the result if (flag == 0 ) System.out.print( "Yes\n" ); else System.out.print( "No\n" ); } // Driver Code public static void main(String[] args) { Node root = newNode( 1 ); root.left = newNode( 2 ); root.right = newNode( 3 ); root.left.left = newNode( 4 ); root.left.right = newNode( 3 ); root.right.right = newNode( 4 ); root.right.left = newNode( 4 ); int dist = 7 ; solve(root, dist); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to implement # the above approach # Structure of a Tree node # Function to create a new node mp = {} class newNode: def __init__( self , key): self .key = key self .left = None self .right = None # Function to count the frequency # of node value present in the tree def frequencyCounts(root): global mp if (root = = None ): return mp[root.key] = mp.get(root.key, 0 ) + 1 frequencyCounts(root.left) frequencyCounts(root.right) # Function that returns the max # distance between the nodes that # have the same key def computeDistance(root, value): if (root = = None ): return - 1 left = computeDistance(root.left, value) right = computeDistance(root.right, value) # If right and left subtree # did not have node whose # key is value if (left = = - 1 and right = = - 1 ): # Check if the current node # is equal to value if (root.key = = value): return 1 else : return - 1 # If the left subtree has # no node whose key is equal # to value if (left = = - 1 ): return right + 1 # If the right subtree has # no node whose key is equal # to value if (right = = - 1 ): return left + 1 else : return 1 + max (left, right) return - 1 # Function that finds if the # distance between any same # nodes is at most K def solve(root, dist): # Create the mp to look # for same value of nodes global mp # Counting the frequency # of nodes frequencyCounts(root) flag = 0 for key,value in mp.items(): if (value > 1 ): # If the returned value of # distance is exceeds dist result = computeDistance(root, key) if (result > dist or result = = - 1 ): flag = 1 break # Print the result if flag = = 0 : print ( "Yes" ) else : print ( "No" ) # Driver Code if __name__ = = '__main__' : root = newNode( 1 ) root.left = newNode( 2 ) root.right = newNode( 3 ) root.left.left = newNode( 4 ) root.left.right = newNode( 3 ) root.right.right = newNode( 4 ) root.right.left = newNode( 4 ) dist = 7 solve(root, dist) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ // Structure of a Tree node public class Node { public int key; public 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 count the frequency of // node value present in the tree static void frequencyCounts(Dictionary< int , int > map, Node root) { if (root == null ) return ; if (map.ContainsKey(root.key)) map[root.key] = map[root.key]+1; else map[root.key] = 1; frequencyCounts(map, root.left); frequencyCounts(map, root.right); } // Function that returns the max distance // between the nodes that have the same key static int computeDistance(Node root, int value) { if (root == null ) { return -1; } int left = computeDistance(root.left, value); int right = computeDistance(root.right, value); // If right and left subtree did not // have node whose key is value if (left == -1 && right == -1) { // Check if the current node // is equal to value if (root.key == value) { return 1; } else return -1; } // If the left subtree has no node // whose key is equal to value if (left == -1) { return right + 1; } // If the right subtree has no node // whose key is equal to value if (right == -1) { return left + 1; } else { return 1 + Math.Max(left, right); } } // Function that finds if the distance // between any same nodes is at most K static void solve(Node root, int dist) { // Create the map to look // for same value of nodes Dictionary< int , int > map = new Dictionary< int , int >(); // Counting the frequency of nodes frequencyCounts(map, root); int flag = 0; foreach (KeyValuePair< int , int > it in map) { if (it.Value > 1) { // If the returned value of // distance is exceeds dist int result = computeDistance( root, it.Key); if (result > dist || result == -1) { flag = 1; break ; } } } // Print the result if (flag == 0) Console.Write( "Yes\n" ); else Console.Write( "No\n" ); } // Driver Code public static void Main(String[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(3); root.right.right = newNode(4); root.right.left = newNode(4); int dist = 7; solve(root, dist); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // Javascript Program to implement the above approach // Structure of a Tree node class Node { constructor(key) { this .key = key; this .left = this .right = null ; } } // Function to create a new node function newNode(key) { let temp = new Node(key); return (temp); } // Function to count the frequency of // node value present in the tree function frequencyCounts(map, root) { if (root == null ) return ; if (map.has(root.key)) map.set(root.key, map.get(root.key) + 1); else map.set(root.key, 1); frequencyCounts(map, root.left); frequencyCounts(map, root.right); } // Function that returns the max distance // between the nodes that have the same key function computeDistance(root, value) { if (root == null ) { return -1; } let left = computeDistance(root.left, value); let right = computeDistance(root.right, value); // If right and left subtree did not // have node whose key is value if (left == -1 && right == -1) { // Check if the current node // is equal to value if (root.key == value) { return 1; } else return -1; } // If the left subtree has no node // whose key is equal to value if (left == -1) { return right + 1; } // If the right subtree has no node // whose key is equal to value if (right == -1) { return left + 1; } else { return 1 + Math.max(left, right); } } // Function that finds if the distance // between any same nodes is at most K function solve(root, dist) { // Create the map to look // for same value of nodes let map = new Map(); // Counting the frequency of nodes frequencyCounts(map, root); let flag = 0; map.forEach((values,keys)=>{ if (values > 1) { // If the returned value of // distance is exceeds dist let result = computeDistance(root, keys); if (result > dist || result == -1) { flag = 1; map.clear(); } } }) // Print the result if (flag == 0) document.write( "Yes" ); else document.write( "No" ); } let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(3); root.right.right = newNode(4); root.right.left = newNode(4); let dist = 7; solve(root, dist); </script> |
Yes
Time Complexity: O(N2)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!