text: Sum of all nodes with smaller values at a distance K from a given node in a BST | Java 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: import java . util . * ; public class GFG { static int sum ; static class TreeNode { int data ; TreeNode left ; TreeNode right ; TreeNode ( int data ) { this . data = data ; this . left = null ; this . right = null ; } } ; static void kDistanceDownSum ( TreeNode root , int k ) { if ( root == null k < 0 ) return ; if ( k == 0 ) { sum += root . data ; return ; } kDistanceDownSum ( root . left , k - 1 ) ; kDistanceDownSum ( root . right , k - 1 ) ; } static int kDistanceSum ( TreeNode root , int target , int k ) { if ( root == null ) return - 1 ; if ( root . data == target ) { kDistanceDownSum ( root . left , k - 1 ) ; return 0 ; } int dl = - 1 ; if ( target < root . data ) { dl = kDistanceSum ( root . left , target , k ) ; } 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 ) ; } if ( dr != - 1 ) { if ( dr + 1 == k ) sum += root . data ; else kDistanceDownSum ( root . left , k - dr - 2 ) ; return 1 + dr ; } return - 1 ; } static 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 ; } static void findSum ( TreeNode root , int target , int K ) { sum = 0 ; kDistanceSum ( root , target , K ) ; System . out . print ( sum ) ; } public static void main ( String [ ] args ) { 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 ) ; } }