Distribute Coins in Binary Tree

MediumTreestree dp

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

You are given the root of a binary tree with n nodes. Each node's value is the number of coins sitting on it, and the total number of coins across the tree is exactly n. In one move you may take a single coin and move it along one edge, from a node to its parent or to one of its children. Return the **minimum** number of moves needed so that every node ends up with exactly one coin. Hint at the target: an O(n) post-order traversal is enough.

Examples

Input: root = [3,0,0]
Output: 2
Move one coin from the root to each child.
Input: root = [0,3,0]
Output: 3
Move two coins from the left child up to the root, then one of them down to the right child.

Constraints

  • 1 <= n <= 100
  • 0 <= Node.val <= n
  • The sum of all Node.val equals n

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 tree dp problems