Cut Branches Without Ones

Medium

You are given the root of a binary tree in which every node holds 0 or 1. Remove every subtree that contains no 1 at all (the subtree of a node is the node together with all of its descendants). Return the root of what remains, or None if nothing does.

Example 1

root=tree_node([0, 1, 0, None, None, 0, 0]) → [0, 1]

The root's right branch is all zeros and gets cut. The root itself is 0, but there is a 1 below it, so it stays.

Example 2

root=tree_node([1, 0, 0, 0, 1]) → [1, 0, None, None, 1]

The left child stays because of the 1 under it on the right, while its zero child on the left goes; the root's right child is a lone zero and goes too.

Example 3

root=tree_node([0, 0]) → None

There are no 1s at all, so nothing is left and the answer is an empty tree.

Constraints

1 ≤ number of nodes ≤ 200
Node.val is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Tree

Similar problems

Is It a Search Tree? Medium Two Mixed-Up Nodes Medium All Leaf Paths With a Given Total Medium Tree Into a Right Chain Medium Digit Branch Totals Medium

Input

root=tree_node([0, 1, 0, None, None, 0, 0])

Expected

[0, 1]

Run checks the first 3 tests in your browser. Submit checks all 83 tests on the server, hidden ones included.