One Coin per Node

Medium

You are given a binary tree with n nodes. Each node holds node.val coins, and there are exactly n coins in the whole tree. In one move you may pass a single coin between two adjacent nodes, from a parent to a child or from a child to a parent. Return the fewest moves needed so that every node ends up with exactly one coin.

Example 1

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

Two coins go from the right child up to the root (2 moves), then one of them goes from the root to the left child (1 move). That is 3 in total.

Example 2

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

The node holding 2 has one spare coin, which moves down to its child in one step.

Example 3

root=tree_node([1]) → 0

Constraints

1 ≤ n ≤ 10⁵
0 ≤ node.val
The values node.val add up to n

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, 0, 3])

Expected

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