Sum of all nodes with smaller values at a distance K from a given node in a BST | Structure of Tree ; Constructor ; Function to add the node to the sum below the target node ; Base Case ; If Kth distant node is reached ; Recur for the left and the right subtrees ; Function to find the K distant nodes from target node , it returns - 1 if target node is not present in tree ; Base Case 1 ; If target is same as root . ; Recurr for the left subtree ; Tree is BST so reduce the search space ; Check if target node was found in left subtree ; If root is at distance k from the target ; Node less than target will be present in left ; When node is not present in the left subtree ; If Kth distant node is reached ; Node less than target at k distance maybe present in the left tree ; If target was not present in the left nor in right subtree ; Function to insert a node in BST ; If root is null ; Insert the data in right half ; Insert the data in left half ; Return the root node ; Function to find the sum of K distant nodes from the target node having value less than target node ; Stores the sum of nodes having values < target at K distance ; Print the resultant sum ; Driver Code ; Create the Tree
let sum = 0 ; class TreeNode { constructor ( data = " " , left = null , right = null ) { this . data = data ; this . left = left ; this . right = right ; } } function kDistanceDownSum ( root , k ) { if ( root == null k < 0 ) { return } if ( k == 0 ) { sum += root . data ; return ; } kDistanceDownSum ( root . left , k - 1 ) ; kDistanceDownSum ( root . right , k - 1 ) ; } function kDistanceSum ( root , target , k ) { if ( root == null ) return - 1 ; if ( root . data == target ) { kDistanceDownSum ( root . left , k - 1 ) ; return 0 ; } let dl = - 1 ; if ( target < root . data ) { dl = kDistanceSum ( root . left , target , k ) ; } if ( dl != - 1 ) { if ( dl + 1 == k ) sum += root . data ; return - 1 ; } let dr = - 1 ; if ( target > root . data ) { dr = kDistanceSum ( root . right , target , k ) ; } if ( dr != - 1 ) { if ( dr + 1 == k ) sum += root . data ; else kDistanceDownSum ( root . left , k - dr - 2 ) ; return 1 + dr ; } return - 1 ; } function insertNode ( data , root ) { if ( root == null ) { let node = new TreeNode ( data ) ; return node ; } else if ( data > root . data ) { root . right = insertNode ( data , root . right ) ; } else if ( data <= root . data ) { root . left = insertNode ( data , root . left ) ; } return root ; } function findSum ( root , target , K ) { kDistanceSum ( root , target , K , sum ) ; document . write ( sum ) ; } let root = null ; let N = 11 ; let tree = [ 3 , 1 , 7 , 0 , 2 , 5 , 10 , 4 , 6 , 9 , 8 ] ; for ( let i = 0 ; i < N ; i ++ ) { root = insertNode ( tree [ i ] , root ) ; } let target = 7 ; let K = 2 ; findSum ( root , target , K ) ;