Distribute Coins in Binary Tree

Problem Statement : 

Distribute Coins in Binary Tree

Given the root of a binary tree with N nodes, each node in the tree has node.val coins, and there are N coins total.
In one move, we may choose two adjacent nodes and move one coin from one node to another.  (The move may be from parent to child, or from child to parent.)
Return the number of moves required to make every node have exactly one coin.

Solution : 

The first time I saw this question it was difficult to guess what is expected and seemed to be tough, but after discussing with my partner we came up with the solution.

The coins needs to be distributed across the tree, we at every node are returning the number coins required from left & right (which can be negative as well) and -1 (for the node itself) and passing up the tree. Whatever the requirement comes from left and right(which can be negative as well, if coins are needed) are the number of moves hence we are taking absolute value to count.
Below is the implementation.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

class Node { public Node left; public Node right; public int data; public Node(int data) { this.data =data; } } /** * Distribute Coins across the Tree */ public class DistributeCoins { private int result = 0; public int getMoves(Node root) { result = 0; distribute(root); return result; } private int distribute(Node root) { if(root == null) return 0; int left = distribute(root.left); int right = distribute(root.right); result += Math.abs(left) + Math.abs(right); return root.data + left + right - 1 ; } public static void main(String[] args) { DistributeCoins obj = new DistributeCoins(); Node root = new Node(1); root.left = new Node(0); root.right = new Node(2); int moves = obj.getMoves(root); System.out.print("Number of Moves : " + moves); } }

Thanks for visiting us.
Happy Coding !! :)