Smallest Subtree with all the Deepest Nodes | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct TreeNode { int val ; TreeNode * left ; TreeNode * right ; TreeNode ( int data ) { this -> val = data ; left = NULL ; right = NULL ; } } ; int find_ht ( TreeNode * root ) { if ( ! root ) return 0 ; if ( root -> left == NULL && root -> right == NULL ) return 1 ; return max ( find_ht ( root -> left ) , find_ht ( root -> right ) ) + 1 ; } void find_node ( TreeNode * root , TreeNode * & req_node ) { if ( ! root ) return ; int left_ht = find_ht ( root -> left ) ; int right_ht = find_ht ( root -> right ) ; if ( left_ht > right_ht ) { find_node ( root -> left , req_node ) ; } else if ( right_ht > left_ht ) { find_node ( root -> right , req_node ) ; } else { req_node = root ; return ; } } int main ( ) { struct TreeNode * root = new TreeNode ( 1 ) ; root -> left = new TreeNode ( 2 ) ; root -> right = new TreeNode ( 3 ) ; TreeNode * req_node = NULL ; find_node ( root , req_node ) ; cout << req_node -> val ; return 0 ; }