algoadvance

Leetcode 865. Smallest Subtree with all the Deepest Nodes

Problem Statement

Given the root of a binary tree, return the smallest subtree such that it contains all the deepest nodes in 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.

Clarifying Questions

  1. What is the definition of depth in this context?
    • The depth of a node is the number of edges from the root to that node.
  2. What are the constraints on the node values and the number of nodes in the binary tree?
    • The number of nodes in the tree is between 1 and 500.
    • Node values are unique integers.
  3. Can the tree have duplicate values?
    • No, node values are unique.
  4. What should we return if there are multiple smallest subtrees with the deepest nodes?
    • In this problem, there will be only one smallest subtree that contains all the deepest nodes.

Strategy

  1. Depth-First Search (DFS):
    • Use DFS to traverse the tree and calculate, for each node, the depth of the deepest node and find the subtree containing all the deepest nodes.
    • A node’s depth is the maximum depth of its children plus one.
    • If the left and right children are of equal depth and that depth is the deepest, then the current node is part of the smallest subtree that contains all the deepest nodes.
  2. Helper Function:
    • A helper function will return a pair containing the depth and the currently considered subtree.
  3. Implementation:
    • Traverse the tree using DFS.
    • Calculate the depth of each node and determine if it should be part of the smallest subtree containing all the deepest nodes.

Code

#include <iostream>
#include <utility> // for std::pair

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    std::pair<int, TreeNode*> dfs(TreeNode* root) {
        if (!root) return {0, nullptr};
        
        auto left = dfs(root->left);
        auto right = dfs(root->right);
        
        int leftDepth = left.first;
        int rightDepth = right.first;
        
        if (leftDepth == rightDepth) {
            return {leftDepth + 1, root};
        } else if (leftDepth > rightDepth) {
            return {leftDepth + 1, left.second};
        } else {
            return {rightDepth + 1, right.second};
        }
    }
    
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return dfs(root).second;
    }
};

// Example to use the solution
int main() {
    // Construct a binary tree
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(5);
    root->right = new TreeNode(1);
    root->left->left = new TreeNode(6);
    root->left->right = new TreeNode(2);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(8);
    root->left->right->left = new TreeNode(7);
    root->left->right->right = new TreeNode(4);

    // Get the solution
    Solution solution;
    TreeNode* result = solution.subtreeWithAllDeepest(root);
    
    // Print the result value
    if (result) {
        std::cout << "The smallest subtree containing all the deepest nodes is rooted at node with value: " << result->val << std::endl;
    }

    // Cleaning up the dynamically allocated memory
    // In a real application, you should free all allocated nodes.
    
    return 0;
}

Time Complexity

The provided solution ensures efficient traversal and subtree determination, keeping the complexity within acceptable bounds even for the upper limit of node count.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI