algoadvance

Leetcode 814. Binary Tree Pruning

Problem Statement

Given the root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

A subtree of a node node is node plus every node that is a descendant of node.

Clarifying Questions

1. Q: Will the tree contain only binary digits (0 and 1)?
   • A: Yes, each node in the binary tree contains only 0 or 1.
2. Q: Can the tree be empty (i.e., root is null)?
   • A: Yes, the tree can be empty, and in that case, the return value should be null.
3. Q: What should be the output if the whole tree contains only zeros?
   • A: The whole tree should be pruned and the output should be null.

Strategy

To solve this problem, we can utilize a recursive approach to traverse the tree in a post-order manner (left-right-root). At each node, we will:

1. Recursively prune the left and right subtrees.
2. Determine whether the current node should be pruned by checking if both its left and right subtrees are null and the node’s own value is 0.
3. Return the root reference if the node is not pruned, otherwise, return null.

This ensures that subtrees that do not contain a 1 are removed from the tree.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        // Base case: if root is null, return null
        if (root == null) {
            return null;
        }

        // Recursively prune the left and right subtrees
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);

        // If both left and right are null, and the current node value is 0, prune it (return null)
        if (root.left == null && root.right == null && root.val == 0) {
            return null;
        }

        // Otherwise, return the current node
        return root;
    }
}

Time Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.
• Space Complexity: O(H), where H is the height of the tree. This space complexity is due to the recursion stack, which, in the worst case (for an unbalanced tree), can approach O(N). For a balanced tree, the space complexity is O(log N).

This approach ensures that we traverse and modify the tree efficiently, removing subtrees that do not contain a 1.

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

• 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?