Smallest Subtree with all the Deepest Nodes

To solve the Smallest Subtree with all the Deepest Nodes problem, I would use a post-order depth-first search approach. This allows us to determine the answer in a single pass through the tree. My strategy involves defining a helper function that returns a pair: the maximum depth of the current subtree and the corresponding LCA node. First, I handle the base cases. If the current node is null, I return a depth of zero and a null pointer. If the node is a leaf, the max depth is one, and the node itself is the LCA. Next, I recursively process the left and right children. Let's say the left child returns a depth of dL and the right child returns dR. If dL equals dR, it means the deepest nodes are distributed across both branches at the same level, making the current node the lowest common ancestor. In this scenario, I return the current node with a depth of dL plus one. However, if one side is deeper than the other, the deepest nodes must be entirely within that deeper subtree. Therefore, I simply propagate the result from the deeper child up the tree, incrementing the depth by one. This ensures we always bubble up the correct LCA while tracking the global maximum depth. This solution achieves O(N) time complexity since we visit each node exactly once, and O(H) space for the recursion stack, which aligns well with Meta's expectation for efficient, scalable algorithms.