Check if all the Nodes in a Binary Tree having common values are at least D distance apart | 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
class Node { constructor ( key ) { this . key = key ; this . left = this . right = null ; } } function newNode ( key ) { let temp = new Node ( key ) ; return ( temp ) ; } 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 computeDistance ( root , value ) { if ( root == null ) { return - 1 ; } let left = computeDistance ( root . left , value ) ; let 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 ) ; } } function solve ( root , dist ) { let map = new Map ( ) ; frequencyCounts ( map , root ) ; let flag = 0 ; map . forEach ( ( values , keys ) => { if ( values > 1 ) { let result = computeDistance ( root , keys ) ; if ( result > dist result == - 1 ) { flag = 1 ; map . clear ( ) ; } } } ) if ( flag == 0 ) document . write ( " " ) ; else document . write ( " " ) ; } 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 ) ;