algoadvance

You are given the root of a binary tree, where the nodes have unique values. You need to return the smallest subtree such that it contains all the deepest nodes of the original tree.

A node is called the deepest if it has the largest depth possible among any node in the entire tree.

• The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.
• The depth of a node is the number of edges in the path from the root node to it.

Clarifying Questions

1. Q: What do we do if there are multiple subtrees that satisfy the condition? A: The problem guarantees the uniqueness of values in nodes, which implies a unique subtree with the deepest nodes.

2. Q: What is the range of the input size? A: This is not explicitly stated but we can assume typical constraints for binary tree problems, where the number of nodes can be reasonably large (thousands).

3. Q: How do we handle an empty tree? A: An empty tree should return None as there is no subtree to return.

Strategy

To determine the smallest subtree containing all the deepest nodes, we can use a depth-first search (DFS) strategy:

1. Use a helper function that returns two values for each node:
   • Its depth relative to the root.
   • The node if it’s the root of the smallest subtree containing all the deepest nodes.
2. For each node, compare the depths of its children:
   • If both children return the same maximum depth, the current node is the root of the smallest subtree.
   • If the depths are different, choose the child with the greater depth.
3. Traverse the entire tree while keeping track of these values.

Code

# 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:
        def dfs(node):
            if not node:
                return (0, None)  # depth, subtree root
            
            left_depth, left_subtree = dfs(node.left)
            right_depth, right_subtree = dfs(node.right)
            
            # If both subtrees are of same depth
            if left_depth > right_depth:
                return (left_depth + 1, left_subtree)
            elif right_depth > left_depth:
                return (right_depth + 1, right_subtree)
            else:
                return (left_depth + 1, node)
        
        return dfs(root)[1]

# Helper function to build tree and insert nodes
def build_tree_from_list(lst, index=0):
    if index >= len(lst) or lst[index] is None:
        return None
    node = TreeNode(val=lst[index])
    node.left = build_tree_from_list(lst, 2 * index + 1)
    node.right = build_tree_from_list(lst, 2 * index + 2)
    return node

# Example scenario
tree_list = [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4]
root = build_tree_from_list(tree_list)
solution = Solution()
result = solution.subtreeWithAllDeepest(root)
print(result.val)  # Output should be 2 (node containing 7 and 4)

Time Complexity

• The time complexity of this solution is (O(N)) where (N) is the number of nodes in the tree. This is because we traverse each node exactly once.
• The space complexity can be (O(N)) in the worst-case scenario due to the recursion stack in a highly unbalanced tree.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?