Check if all the Nodes in a Binary Tree having common values are at least D distance apart | C ++ program to implement the above approach ; Structure of a Tree node ; Function to create a new node ; Function to count the frequency of node value present in the tree ; Function that returns the max distance between the nodes that have the same key ; If right and left subtree did not have node whose key is value ; Check if the current node is equal to value ; If the left subtree has no node whose key is equal to value ; If the right subtree has no node whose key is equal to value ; Function that finds if the distance between any same nodes is at most K ; Create the map to look for same value of nodes ; Counting the frequency of nodes ; If the returned value of distance is exceeds dist ; Print the result ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int key ; struct Node * left , * right ; } ; Node * newNode ( int key ) { Node * temp = new Node ; temp -> key = key ; temp -> left = temp -> right = NULL ; return ( temp ) ; } void frequencyCounts ( unordered_map < int , int > & map , Node * root ) { if ( root == NULL ) return ; map [ root -> key ] ++ ; frequencyCounts ( map , root -> left ) ; frequencyCounts ( map , root -> right ) ; } int computeDistance ( Node * root , int value ) { if ( root == NULL ) { return -1 ; } int left = computeDistance ( root -> left , value ) ; int right = computeDistance ( root -> right , value ) ; if ( left == -1 && right == -1 ) { if ( root -> key == value ) { return 1 ; } else return -1 ; } if ( left == -1 ) { return right + 1 ; } if ( right == -1 ) { return left + 1 ; } else { return 1 + max ( left , right ) ; } return -1 ; } void solve ( Node * root , int dist ) { unordered_map < int , int > map ; frequencyCounts ( map , root ) ; int flag = 0 ; for ( auto it = map . begin ( ) ; it != map . end ( ) ; it ++ ) { if ( it -> second > 1 ) { int result = computeDistance ( root , it -> first ) ; if ( result > dist result == -1 ) { flag = 1 ; break ; } } } flag == 0 ? cout << " Yes STRNEWLINE " : cout << " No STRNEWLINE " ; } 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 ; }