Equal Tree Partition

MediumTreesdfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given the root of a binary tree, decide whether you can delete **exactly one edge** so that the two resulting trees have the same sum of node values. Deleting the edge between a node and its parent splits off that node's entire subtree. Return true if some edge produces two trees with equal sums, and false otherwise. A tree with a single node has no edges, so the answer is false. Be careful with a total sum of 0: the whole tree itself is not a valid piece, because no edge was removed to produce it.

Examples

Input: root = [3,1,4,null,null,-2,6]
Output: true
The total is 12. Cutting the edge above the leaf 6 leaves two trees that each sum to 6.
Input: root = [1,2,5]
Output: false
The total is 8, but the only removable subtrees sum to 2 and 5, and neither is 4.
Input: root = [0,-1,1]
Output: false
The total is 0, yet the removable subtrees sum to -1 and 1. The whole tree summing to 0 does not count.

Constraints

  • 1 <= number of nodes <= 10^4
  • -10^5 <= Node.val <= 10^5

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs problems