We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest Subtree with all the Deepest Nodes

Number: 896

Difficulty: Medium

Paid? No

Companies: Meta, Salesforce

Problem Description

Given the root of a binary tree, return the smallest subtree such that it contains all the deepest nodes in the original tree. The deepest nodes are those that have the largest distance from the root. The solution is to find the lowest common ancestor (LCA) of all deepest nodes because this node represents the smallest subtree that includes every deepest node.

Key Insights

  • The deepest nodes can be found using a DFS traversal while tracking each node's depth.
  • The problem can be solved by performing a DFS that returns both the candidate subtree (or LCA for deepest nodes) and the height of that subtree.
  • At each node, comparing the maximum depths of its left and right subtrees helps decide:
    • If left and right depths are equal, the current node is the LCA.
    • Otherwise, the deeper subtree contains all the deepest nodes.
  • This recursive strategy efficiently fuses the search for maximum depth and the lowest common ancestor in one traversal.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, as we visit each node once. Space Complexity: O(h) in the recursion stack, where h is the height of the tree (O(n) in the worst-case for skewed trees).

Solution

The solution uses a depth-first search (DFS) to compute for every node the depth of its deepest descendant. As we traverse, each subtree returns both its maximum depth and the candidate node that forms the smallest subtree containing all deepest nodes. At each node:

  1. Recursively get the deepest node and depth for the left and right children.
  2. Compare these depths to determine whether the current node is the common ancestor or if one of the children already covers all deepest nodes.
  3. Return the candidate with the updated maximum depth.

This approach effectively combines depth calculation with the LCA determination.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        # Helper function that returns a tuple (deepest_node_candidate, depth)
        def dfs(node):
            # Base case: if the node is None, return None and depth 0
            if not node:
                return (None, 0)
            # Recursively find for the left child
            left_candidate, left_depth = dfs(node.left)
            # Recursively find for the right child
            right_candidate, right_depth = dfs(node.right)
            
            # Compare depths from left and right subtrees
            if left_depth > right_depth:
                # Left subtree is deeper, use its candidate
                return (left_candidate, left_depth + 1)
            elif left_depth < right_depth:
                # Right subtree is deeper, use its candidate
                return (right_candidate, right_depth + 1)
            else:
                # Both subtrees have the same depth, current node is common ancestor
                return (node, left_depth + 1)
        
        # The candidate from the DFS is the root of the smallest subtree containing all deepest nodes.
        candidate, _ = dfs(root)
        return candidate
← Back to All Questions