Smallest Subtree With All The Deepest Nodes - Leetcode Solution

The problem "Smallest Subtree With All The Deepest Nodes" on LeetCode asks to find the smallest subtree in a given binary tree that contains all the deepest nodes.

Approach:

The solution for this problem involves finding the depth of each node in the tree and then determining the nodes at the maximum depth. After that, we will proceed to find the Lowest Common Ancestor (LCA) for all the deepest nodes. The LCA is the smallest subtree that contains all these nodes.

Step 1 : Find the Maximum Depth of the Binary Tree

First, we need to find the maximum depth of the binary tree. For this, we can use Depth First Search (DFS) or Breadth First Search (BFS) algorithm.

Step 2 : Find Nodes at Maximum Depth

Once we have found the maximum depth, we need to identify the nodes at this depth level. For every node, we need to check if its depth is equal to the maximum depth. We can do this recursively for each node by keeping track of its depth level.

Step 3 : Find LCA of Nodes at Maximum Depth

After we have found all the nodes at the maximum depth, we need to find the LCA of these nodes. We can use DFS algorithm to traverse the tree, and whenever we find a node that is a common ancestor of the deepest nodes, we mark it.

At the end of the traversal, we will have marked all common ancestors of the deepest nodes. The last marked node is the LCA that we want.

Step 4 : Return the LCA Node

Finally, we return the LCA node as the result, which is the smallest subtree that contains all the deepest nodes.

Implementation:

Here's the Python code for Smallest Subtree With All The Deepest Nodes problem on LeetCode:

class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        
        # Step 1 : Find the Maximum Depth of the Binary Tree
        def maxDepth(node):
            if node is None:
                return 0
            else:
                leftDepth = maxDepth(node.left)
                rightDepth = maxDepth(node.right)
                return max(leftDepth, rightDepth) + 1
        
        # Step 2 : Find Nodes at Maximum Depth
        def nodesAtMaxDepth(node, currDepth, maxDepth):
            if node is None:
                return []
            if currDepth == maxDepth:
                return [node]
            leftNodes = nodesAtMaxDepth(node.left, currDepth+1, maxDepth)
            rightNodes = nodesAtMaxDepth(node.right, currDepth+1, maxDepth)
            return leftNodes + rightNodes
        
        # Step 3 : Find LCA of Nodes at Maximum Depth
        def LCA(node, nodes):
            if node is None:
                return None
            if node in nodes:
                return node
            leftLCA = LCA(node.left, nodes)
            rightLCA = LCA(node.right, nodes)
            if leftLCA is not None and rightLCA is not None:
                return node
            if leftLCA is not None:
                return leftLCA
            else:
                return rightLCA
        
        # Step 4 : Return the LCA Node
        maxdepth = maxDepth(root)
        nodes = nodesAtMaxDepth(root, 1, maxdepth)
        return LCA(root, nodes)

1