Given a Binary Tree, the task is to find the smallest subtree that contains all the deepest nodes of the given Binary Tree and return the root of that subtree.
Note: Depth of each node is defined as the length of the path from the root to the given node.
Examples:
Input:
1 / \ 2 3 / \ / \ 4 5 6 7 / \ 8 9Output: 7
Input:
1 / \ 2 3Output: 1
Approach: Follow the steps below to solve the problem:
- Traverse the Binary Tree recursively using DFS .
- For every node, find the depth of its left and right subtrees.
- If depth of the left subtree > depth of the right subtree: Traverse the left subtree.
- If depth of the right subtree > depth of the left subtree: Traverse the right subtree.
- Otherwise, return the current node.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Structure of a Nodestruct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int data) { this->val = data; left = NULL; right = NULL; }};// Function to return depth of// the Tree from rootint find_ht(TreeNode* root){ if (!root) return 0; // If current node is a leaf node if (root->left == NULL && root->right == NULL) return 1; return max(find_ht(root->left), find_ht(root->right)) + 1;}// Function to find the root of the smallest// subtree consisting of all deepest nodesvoid find_node(TreeNode* root, TreeNode*& req_node){ if (!root) return; // Stores height of left subtree int left_ht = find_ht(root->left); // Stores height of right subtree int right_ht = find_ht(root->right); // If height of left subtree exceeds // that of the right subtree if (left_ht > right_ht) { // Traverse left subtree find_node(root->left, req_node); } // If height of right subtree exceeds // that of the left subtree else if (right_ht > left_ht) { find_node(root->right, req_node); } // Otherwise else { // Return current node req_node = root; return; }}// Driver Codeint 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;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Structure of a Nodestatic class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int data) { this.val = data; left = null; right = null; }};// Function to return depth of// the Tree from rootstatic int find_ht(TreeNode root){ if (root == null) return 0; // If current node is a leaf node if (root.left == null && root.right == null) return 1; return Math.max(find_ht(root.left), find_ht(root.right)) + 1;}// Function to find the root of the smallest// subtree consisting of all deepest nodesstatic TreeNode find_node(TreeNode root, TreeNode req_node){ if (root == null) return req_node; // Stores height of left subtree int left_ht = find_ht(root.left); // Stores height of right subtree int right_ht = find_ht(root.right); // If height of left subtree exceeds // that of the right subtree if (left_ht > right_ht) { // Traverse left subtree req_node = find_node(root.left, req_node); } // If height of right subtree exceeds // that of the left subtree else if (right_ht > left_ht) { req_node = find_node(root.right, req_node); } // Otherwise else { // Return current node req_node = root; return req_node; } return req_node;}// Driver Codepublic 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);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement# the above approach# Structure of a Nodeclass TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None# Function to return depth of# the Tree from rootdef find_ht(root): if (not root): return 0 # If current node is a leaf node if (root.left == None and root.right == None): return 1 return max(find_ht(root.left), find_ht(root.right)) + 1# Function to find the root of the smallest# subtree consisting of all deepest nodesdef find_node(root): global req_node if (not root): return # Stores height of left subtree left_ht = find_ht(root.left) # Stores height of right subtree right_ht = find_ht(root.right) # If height of left subtree exceeds # that of the right subtree if (left_ht > right_ht): # Traverse left subtree find_node(root.left) # If height of right subtree exceeds # that of the left subtree elif (right_ht > left_ht): find_node(root.right) # Otherwise else: # Return current node req_node = root return# Driver Codeif __name__ == '__main__': root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) req_node = None find_node(root) print(req_node.val) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;class GFG{// Structure of a Nodepublic class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode(int data) { this.val = data; left = null; right = null; }};// Function to return depth of// the Tree from rootstatic int find_ht(TreeNode root){ if (root == null) return 0; // If current node is a leaf node if (root.left == null && root.right == null) return 1; return Math.Max(find_ht(root.left), find_ht(root.right)) + 1;}// Function to find the root of the smallest// subtree consisting of all deepest nodesstatic TreeNode find_node(TreeNode root, TreeNode req_node){ if (root == null) return req_node; // Stores height of left subtree int left_ht = find_ht(root.left); // Stores height of right subtree int right_ht = find_ht(root.right); // If height of left subtree exceeds // that of the right subtree if (left_ht > right_ht) { // Traverse left subtree req_node = find_node(root.left, req_node); } // If height of right subtree exceeds // that of the left subtree else if (right_ht > left_ht) { req_node = find_node(root.right, req_node); } // Otherwise else { // Return current node req_node = root; return req_node; } return req_node;}// Driver Codepublic 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); Console.Write(req_node.val);}}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for above approach // Structure of a Node class TreeNode { constructor(data) { this.left = null; this.right = null; this.val = data; } } // Function to return depth of // the Tree from root function find_ht(root) { if (root == null) return 0; // If current node is a leaf node if (root.left == null && root.right == null) return 1; return Math.max(find_ht(root.left), find_ht(root.right)) + 1; } // Function to find the root of the smallest // subtree consisting of all deepest nodes function find_node(root, req_node) { if (root == null) return req_node; // Stores height of left subtree let left_ht = find_ht(root.left); // Stores height of right subtree let right_ht = find_ht(root.right); // If height of left subtree exceeds // that of the right subtree if (left_ht > right_ht) { // Traverse left subtree req_node = find_node(root.left, req_node); } // If height of right subtree exceeds // that of the left subtree else if (right_ht > left_ht) { req_node = find_node(root.right, req_node); } // Otherwise else { // Return current node req_node = root; return req_node; } return req_node; } let root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); let req_node = null; req_node = find_node(root, req_node); document.write(req_node.val); </script> |
Output:
1
Time Complexity: O(NlogN)
The worst-case complexity occurs for skewed Binary Tree, whose traversal of either left or right subtree requires O(N) complexity and calculating height of subtrees requires O(logN) computational complexity.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
