Closest leaf to a given node in Binary Tree | A binary tree node ;  ; This function finds closest leaf to root . This distance is stored at * minDist . ; base case ; If this is a leaf node , then check if it is closer than the closest so far ; Recur for left and right subtrees ; This function finds if there is closer leaf to x through parent node . ; Base cases ; Search x in left subtree of root ; If left subtree has x ; Find closest leaf in right subtree ; Search x in right subtree of root ; If right subtree has x ; Find closest leaf in left subtree ; Returns minimum distance of a leaf from given node x ; Initialize result ( minimum distance from a leaf ) ; Find closest leaf down to x ; See if there is a closer leaf through parent ; Driver program ; Let us create Binary Tree shown in above example
class Node { int key ; Node left , right ; public Node ( int key ) { this . key = key ; left = right = null ; } } class Distance { int minDis = Integer . MAX_VALUE ; } class BinaryTree { Node root ; void findLeafDown ( Node root , int lev , Distance minDist ) { if ( root == null ) return ; if ( root . left == null && root . right == null ) { if ( lev < ( minDist . minDis ) ) minDist . minDis = lev ; return ; } findLeafDown ( root . left , lev + 1 , minDist ) ; findLeafDown ( root . right , lev + 1 , minDist ) ; } int findThroughParent ( Node root , Node x , Distance minDist ) { if ( root == null ) return - 1 ; if ( root == x ) return 0 ; int l = findThroughParent ( root . left , x , minDist ) ; if ( l != - 1 ) { findLeafDown ( root . right , l + 2 , minDist ) ; return l + 1 ; } int r = findThroughParent ( root . right , x , minDist ) ; if ( r != - 1 ) { findLeafDown ( root . left , r + 2 , minDist ) ; return r + 1 ; } return - 1 ; } int minimumDistance ( Node root , Node x ) { Distance d = new Distance ( ) ; findLeafDown ( x , 0 , d ) ; findThroughParent ( root , x , d ) ; return d . minDis ; } public static void main ( String [ ] args ) { BinaryTree tree = new BinaryTree ( ) ; tree . root = new Node ( 1 ) ; tree . root . left = new Node ( 12 ) ; tree . root . right = new Node ( 13 ) ; tree . root . right . left = new Node ( 14 ) ; tree . root . right . right = new Node ( 15 ) ; tree . root . right . left . left = new Node ( 21 ) ; tree . root . right . left . right = new Node ( 22 ) ; tree . root . right . right . left = new Node ( 23 ) ; tree . root . right . right . right = new Node ( 24 ) ; tree . root . right . left . left . left = new Node ( 1 ) ; tree . root . right . left . left . right = new Node ( 2 ) ; tree . root . right . left . right . left = new Node ( 3 ) ; tree . root . right . left . right . right = new Node ( 4 ) ; tree . root . right . right . left . left = new Node ( 5 ) ; tree . root . right . right . left . right = new Node ( 6 ) ; tree . root . right . right . right . left = new Node ( 7 ) ; tree . root . right . right . right . right = new Node ( 8 ) ; Node x = tree . root . right ; System . out . println ( " The ▁ closest ▁ leaf ▁ to ▁ node ▁ with ▁ value ▁ " + x . key + " ▁ is ▁ at ▁ a ▁ distance ▁ of ▁ " + tree . minimumDistance ( tree . root , x ) ) ; } }