Smallest Subtree with all the Deepest Nodes

0 0 6 minutes read

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    9

Output: 7

Input:

               1
             /   \
            2     3

Output: 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 Node
struct 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 root
int 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 nodes
void 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 Code
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;
}

Java

// Java program to implement
// the above approach
import java.util.*;
class GFG
{
 
// Structure of a Node
static 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 root
static 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 nodes
static 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 Code
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);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to implement
# the above approach
 
# Structure of a Node
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
 
# Function to return depth of
# the Tree from root
def 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 nodes
def 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 Code
if __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 approach
using System;
 
class GFG
{
 
// Structure of a Node
public 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 root
static 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 nodes
static 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 Code
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);
    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:

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 zambiatek!