algoadvance

Leetcode 814. Binary Tree Pruning

Problem Statement

You are given the root of a binary tree where each node has a value of 0 or 1. Prune the tree so that subtrees containing all 0s are removed. A subtree of a node node is node plus every node that is a descendant of node.

Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

Clarifying Questions

  1. What does the structure of a binary tree node look like? Typically, a binary tree node in C++ might be defined as follows: 
    struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

  2. Can the input tree be empty? Yes, the input tree can be empty (root could be nullptr).

  3. What should be returned if the entire tree is pruned? If the entire tree is pruned, return nullptr.

Strategy

  1. Post-order Traversal
    • For each node, first process its left and right subtrees.
    • If any subtree does not contain a 1, set the respective child pointer to nullptr.
  2. Recursive Function
    • Define a recursive function that performs the pruning and returns the pruned tree.
    • The base case would be when the node is nullptr.
    • Recursively prune the left and right subtrees.
    • Determine whether to prune the current node based on its value and the status of its children.

Time Complexity

Code

Here’s an implementation in C++:

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

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if (!root) {
            return nullptr;
        }
        
        // Recursively prune the left and right subtrees
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        
        // If the current node's value is 0 and both subtrees are nullptr, prune this node
        if (root->val == 0 && !root->left && !root->right) {
            return nullptr;
        }
        
        return root;
    }
};

Explanation

  1. Recursive Pruning:
    • Start with the root node and recursively check the left and right children.
  2. Pruning Condition:
    • After processing the left and right children, the current node is pruned if its value is 0 and if both its left and right children are nullptr.
  3. Return the Pruned Tree:
    • Return the root (pruned) for each recursive call.

This approach ensures that unnecessary nodes are removed efficiently while preserving nodes that have or are required by nodes with the value 1.

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