Check if all the Nodes in a Binary Tree having common values are at least D distance apart | Java 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
import java . util . * ; class GFG { static class Node { int key ; Node left , right ; } ; static Node newNode ( int key ) { Node temp = new Node ( ) ; temp . key = key ; temp . left = temp . right = null ; return ( temp ) ; } 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 ) ; } 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 ( 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 + Math . max ( left , right ) ; } } static void solve ( Node root , int dist ) { HashMap < Integer , Integer > map = new HashMap < Integer , Integer > ( ) ; frequencyCounts ( map , root ) ; int flag = 0 ; for ( Map . Entry < Integer , Integer > it : map . entrySet ( ) ) { if ( it . getValue ( ) > 1 ) { int result = computeDistance ( root , it . getKey ( ) ) ; if ( result > dist result == - 1 ) { flag = 1 ; break ; } } } if ( flag == 0 ) System . out . print ( "YesNEW_LINE"); else System . out . print ( "NoNEW_LINE"); } 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 ) ; } }