#814

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Binary Tree Pruning

Binary Tree Pruning removes subtrees not containing a 1, applying binary-tree traversal with state tracking.

Problem Statement

Given the root of a binary tree, return the same tree where every subtree not containing a 1 has been removed. A subtree of a node is defined as the node itself and every descendant node connected to it.

For example, in a tree with nodes valued 0 or 1, prune all subtrees that do not contain at least one node with the value 1. This problem can be solved efficiently using binary-tree traversal techniques combined with state tracking to determine which subtrees to keep or prune.

Examples

Example 1

Input: root = [1,null,0,0,1]

Output: [1,null,0,null,1]

Only the red nodes satisfy the property "every subtree not containing a 1". The diagram on the right represents the answer.

Example 2

Input: root = [1,0,1,0,0,0,1]

Output: [1,null,1,null,1]

Example details omitted.

Example 3

Input: root = [1,1,0,1,1,0,1,0]

Output: [1,1,0,1,1,null,1]

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 200].
Node.val is either 0 or 1.

Solution Approach

Postorder Depth-First Search (DFS)

A common approach for solving this problem is to perform a postorder DFS traversal. Starting from the leaves of the tree, recursively check each node's subtrees to determine if they contain a 1. If a subtree does not contain a 1, it is pruned (set to null). This ensures that subtrees without the required value are removed before processing the parent node.

State Tracking

To implement the solution efficiently, use state tracking to determine whether a node or its subtree should be pruned. As you traverse the tree, keep track of whether a node has a descendant with the value 1. This state information is passed up the tree to decide whether to prune the current node's subtree or not.

In-place Tree Modification

The pruning should be done in place without needing to create additional data structures. Modify the tree as you traverse, ensuring the tree structure remains intact but with the required subtrees pruned. This approach minimizes the space complexity and efficiently modifies the tree as needed.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the algorithm is O(n), where n is the number of nodes in the tree. This is because each node is visited once during the DFS traversal. The space complexity depends on the depth of the recursion stack, which in the worst case (for a skewed tree) is O(n), but in the average case (balanced tree), it is O(log n).

What Interviewers Usually Probe

The candidate should demonstrate understanding of binary tree traversal techniques like DFS.
The candidate should be able to describe efficient state tracking methods and how they apply to pruning.
The candidate should mention in-place tree modification and the importance of space optimization.

Common Pitfalls or Variants

Common pitfalls

Failing to perform a postorder traversal, which may lead to incorrect pruning.
Not maintaining state information correctly, leading to the retention of unnecessary subtrees.
Creating additional data structures unnecessarily, which can increase the space complexity of the solution.

Follow-up variants

Pruning only specific subtrees based on different criteria (e.g., pruning if the sum of nodes in the subtree is less than a certain threshold).
Handling larger trees with optimizations like iterative DFS to avoid stack overflow for deep trees.
Adapting the solution for binary search trees (BST), where the tree structure may influence traversal strategies.

FAQ

How does Binary Tree Pruning work?

Binary Tree Pruning involves performing a tree traversal (typically postorder DFS) to remove subtrees that do not contain a node with the value 1.

What is the time complexity of Binary Tree Pruning?

The time complexity is O(n), where n is the number of nodes in the tree, since each node is visited once during the traversal.

How does state tracking help in Binary Tree Pruning?

State tracking ensures that only subtrees containing a 1 are retained. As you traverse the tree, you track whether each node or its subtree contains a 1, determining if it should be pruned.

What are the common pitfalls in solving Binary Tree Pruning?

Common pitfalls include not performing a postorder DFS, failing to correctly track state, or using additional data structures that increase space complexity unnecessarily.

How does GhostInterview assist with Binary Tree Pruning?

GhostInterview provides step-by-step guidance, ensures correct traversal and pruning implementation, and offers feedback on optimizing both space and time complexity for Binary Tree Pruning.

terminal

Solution

Solution 1: Recursion

First, we check if the current node is null. If it is, we directly return the null node.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return root
        root.left = self.pruneTree(root.left)
        root.right = self.pruneTree(root.right)
        if root.val == 0 and root.left == root.right:
            return None
        return root

Continue Practicing

#783 minimum distance between bst nodes #863 all nodes distance k in binary tree #865 smallest subtree with all the deepest nodes