Is Binary Tree Pruning easy or hard?

Binary Tree Pruning is considered a medium-level problem. The main challenge is recognizing that post-order traversal is required because pruning decisions depend on the results from child subtrees.

How to solve Binary Tree Pruning in O(n)?

Use a post-order depth-first traversal. Recursively process the left and right subtrees first, assigning the returned nodes back to root.left and root.right. After both calls, remove the current node if its value is 0 and both children are null. Each node is processed once, giving O(n) time complexity.

Binary Tree Pruning Python or Java solution?

Both Python and Java solutions typically implement recursive post-order traversal. The function processes left and right children, prunes subtrees returning null when needed, and returns the cleaned node. The logic is identical across languages with O(n) time complexity.

What is the best approach for Binary Tree Pruning?

The best approach is post-order traversal using depth-first search. By processing the left and right children before the current node, you can determine whether a subtree contains a 1. If both children are null and the node value is 0, the subtree is pruned. This approach runs in O(n) time and O(h) space where h is the tree height.

Is Binary Tree Pruning asked at Google/Amazon/Meta?

Binary tree pruning problems appear in variations across major tech interviews, including companies like Amazon, Google, and Meta. Interviewers use it to test tree traversal knowledge, recursion, and bottom-up reasoning with depth-first search.

What data structure is used in Binary Tree Pruning?

The problem uses a binary tree as the primary data structure and depth-first search for traversal. The recursive solution relies on the call stack, while the iterative approach uses an explicit stack to simulate post-order traversal.

What is the time complexity of Binary Tree Pruning?

Binary Tree Pruning runs in O(n) time because every node in the tree is visited exactly once during traversal. The algorithm checks the children and potentially removes a node after processing its subtree. Space complexity is O(h) due to recursion stack or the iterative traversal stack, where h is the height of the tree.

Description Solution Video 18:00

814. Binary Tree Pruning

Medium72.3% acceptance5 companies

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.

Example 1:

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
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 3:

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

Constraints:

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

Asked at 5 companies

Hulu Meta

Google Amazon Microsoft

Topics

18:00

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,null,0,0,1]

Input

[1,0,1,0,0,0,1]

Input

[1,1,0,1,1,0,1,0]

Your code is saved on this device.Solution