One Cut, Two Equal Halves

Medium

You are given the root of a binary tree. Can you remove exactly one edge so that the tree falls apart into two pieces whose node values add up to the same total? Return True if such an edge exists, and False otherwise.

Example 1

root=tree_node([1, 8, 3, None, None, 2, 2]) → True

Cut the edge between the root and node 8: one part sums to 8, the other to 1 + 3 + 2 + 2 = 8.

Example 2

root=tree_node([0, -2, 2]) → False

The total is 0, but the only parts you can cut off are the subtree -2 or the subtree 2, and neither equals half the total, which is 0.

Example 3

root=tree_node([5]) → False

There are no edges, so there is nothing to cut.

Constraints

1 ≤ number of nodes ≤ 10⁵
-10⁵ ≤ Node.val ≤ 10⁵

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([1, 8, 3, None, None, 2, 2])

Expected

True

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