Find the closest element in Binary Search Tree | Recursive Java program to find key closest to k in given Binary Search Tree . ; A binary tree node has key , pointer to left child and a pointer to right child ; Utility that allocates a new node with the given key and null left and right pointers . ; Function to find node with minimum absolute difference with given K min_diff - . minimum difference till now min_diff_key - . node having minimum absolute difference with K ; If k itself is present ; update min_diff and min_diff_key by checking current node value ; if k is less than ptr . key then move in left subtree else in right subtree ; Wrapper over maxDiffUtil ( ) ; Initialize minimum difference ; Find value of min_diff_key ( Closest key in tree with k ) ; Driver program to run the case
class solution { static int min_diff , min_diff_key ; static class Node { int key ; Node left , right ; } ; static Node newnode ( int key ) { Node node = new Node ( ) ; node . key = key ; node . left = node . right = null ; return ( node ) ; } static void maxDiffUtil ( Node ptr , int k ) { if ( ptr == null ) return ; if ( ptr . key == k ) { min_diff_key = k ; return ; } if ( min_diff > Math . abs ( ptr . key - k ) ) { min_diff = Math . abs ( ptr . key - k ) ; min_diff_key = ptr . key ; } if ( k < ptr . key ) maxDiffUtil ( ptr . left , k ) ; else maxDiffUtil ( ptr . right , k ) ; } static int maxDiff ( Node root , int k ) { min_diff = 999999999 ; min_diff_key = - 1 ; maxDiffUtil ( root , k ) ; return min_diff_key ; } public static void main ( String args [ ] ) { Node root = newnode ( 9 ) ; root . left = newnode ( 4 ) ; root . right = newnode ( 17 ) ; root . left . left = newnode ( 3 ) ; root . left . right = newnode ( 6 ) ; root . left . right . left = newnode ( 5 ) ; root . left . right . right = newnode ( 7 ) ; root . right . right = newnode ( 22 ) ; root . right . right . left = newnode ( 20 ) ; int k = 18 ; System . out . println ( maxDiff ( root , k ) ) ; } }