text: Sum of all nodes with smaller values at a distance K from a given node in a BST | C ++ program for the above approach ; 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; struct TreeNode { int data ; TreeNode * left ; TreeNode * right ; TreeNode ( int data ) { this -> data = data ; this -> left = NULL ; this -> right = NULL ; } } ; void kDistanceDownSum ( TreeNode * root , int k , int & sum ) { if ( root == NULL k < 0 ) return ; if ( k == 0 ) { sum += root -> data ; return ; } kDistanceDownSum ( root -> left , k - 1 , sum ) ; kDistanceDownSum ( root -> right , k - 1 , sum ) ; } int kDistanceSum ( TreeNode * root , int target , int k , int & sum ) { if ( root == NULL ) return -1 ; if ( root -> data == target ) { kDistanceDownSum ( root -> left , k - 1 , sum ) ; return 0 ; } int dl = -1 ; if ( target < root -> data ) { dl = kDistanceSum ( root -> left , target , k , sum ) ; } if ( dl != -1 ) { if ( dl + 1 == k ) sum += root -> data ; return -1 ; } int dr = -1 ; if ( target > root -> data ) { dr = kDistanceSum ( root -> right , target , k , sum ) ; } if ( dr != -1 ) { if ( dr + 1 == k ) sum += root -> data ; else kDistanceDownSum ( root -> left , k - dr - 2 , sum ) ; return 1 + dr ; } return -1 ; } TreeNode * insertNode ( int data , TreeNode * root ) { if ( root == NULL ) { TreeNode * 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 ; } void findSum ( TreeNode * root , int target , int K ) { int sum = 0 ; kDistanceSum ( root , target , K , sum ) ; cout << sum ; } int main ( ) { TreeNode * root = NULL ; int N = 11 ; int tree [ ] = { 3 , 1 , 7 , 0 , 2 , 5 , 10 , 4 , 6 , 9 , 8 } ; for ( int i = 0 ; i < N ; i ++ ) { root = insertNode ( tree [ i ] , root ) ; } int target = 7 ; int K = 2 ; findSum ( root , target , K ) ; return 0 ; }