Smallest Subtree with all the Deepest Nodes | Java program to implement the above approach ; Structure of a Node ; Function to return depth of the Tree from root ; If current node is a leaf node ; Function to find the root of the smallest subtree consisting of all deepest nodes ; Stores height of left subtree ; Stores height of right subtree ; If height of left subtree exceeds that of the right subtree ; Traverse left subtree ; If height of right subtree exceeds that of the left subtree ; Otherwise ; Return current node ; Driver Code
import java . util . * ; class GFG { static class TreeNode { int val ; TreeNode left ; TreeNode right ; TreeNode ( int data ) { this . val = data ; left = null ; right = null ; } } ; static int find_ht ( TreeNode root ) { if ( root == null ) return 0 ; if ( root . left == null && root . right == null ) return 1 ; return Math . max ( find_ht ( root . left ) , find_ht ( root . right ) ) + 1 ; } static TreeNode find_node ( TreeNode root , TreeNode req_node ) { if ( root == null ) return req_node ; int left_ht = find_ht ( root . left ) ; int right_ht = find_ht ( root . right ) ; if ( left_ht > right_ht ) { req_node = find_node ( root . left , req_node ) ; } else if ( right_ht > left_ht ) { req_node = find_node ( root . right , req_node ) ; } else { req_node = root ; return req_node ; } return req_node ; } public static void main ( String [ ] args ) { TreeNode root = new TreeNode ( 1 ) ; root . left = new TreeNode ( 2 ) ; root . right = new TreeNode ( 3 ) ; TreeNode req_node = null ; req_node = find_node ( root , req_node ) ; System . out . print ( req_node . val ) ; } }