Given a binary tree with N nodes, in which each node value represents the number of candies present at that node, and there are N candies in total. In one move, one may choose two adjacent nodes and move one candy from one node to another (the move may be from parent to child, or from child to parent.)
The task is to find the number of moves required such that every node has exactly one candy.
Examples:
Input : 3
/ \
0 0
Output : 2
Explanation: From the root of the tree, we move one
candy to its left child, and one candy to
its right child.
Input : 0
/ \
3 0
Output :3
Explanation : From the left child of the root, we move
two candies to the root [taking two moves]. Then, we move
one candy from the root of the tree to the right child.
Recursive Solution:
The idea is to traverse the tree from leaf to root and consecutively balance all of the nodes. To balance a node, the number of candy at that node must be 1.
There can be two cases:
- If a node needs candies, if the node of the tree has 0 candies (an excess of -1 from what it needs), then we should push a candy from its parent onto the node.
- If the node has more than 1 candy. If it has say, 4 candies (an excess of 3), then we should push 3 candies off the node to its parent.
So, the total number of moves from that leaf to or from its parent is excess = abs(num_candies – 1).
Once a node is balanced, we never have to consider this node again in the rest of our calculation.
Below is the implementation of the above approach:
C++
// C++ program to distribute candies// in a Binary Tree#include <bits/stdc++.h>using namespace std;// Binary Tree Nodestruct Node { int key; struct Node *left, *right;};// Utility function to create a new nodeNode* newNode(int key){ Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp);}// Utility function to find the number of// moves to distribute all of the candiesint distributeCandyUtil(Node* root, int& ans){ // Base Case if (root == NULL) return 0; // Traverse left subtree int l = distributeCandyUtil(root->left, ans); // Traverse right subtree int r = distributeCandyUtil(root->right, ans); // Update number of moves ans += abs(l) + abs(r); // Return number of moves to balance // current node return root->key + l + r - 1;}// Function to find the number of moves to// distribute all of the candiesint distributeCandy(Node* root){ int ans = 0; distributeCandyUtil(root, ans); return ans;}// Driver programint main(){ /* 3 / \ 0 0 Let us create Binary Tree shown in above example */ Node* root = newNode(3); root->left = newNode(0); root->right = newNode(0); cout << distributeCandy(root); return 0;} |
Java
// Java program to distribute candies// in a Binary Treeclass GfG { // Binary Tree Node static class Node { int key; Node left, right; } static int ans = 0; // Utility function to create a new node static Node newNode(int key) { Node temp = new Node(); temp.key = key; temp.left = null; temp.right = null; return (temp); } // Utility function to find the number of // moves to distribute all of the candies static int distributeCandyUtil(Node root) { // Base Case if (root == null) return 0; // Traverse left subtree int l = distributeCandyUtil(root.left); // Traverse right subtree int r = distributeCandyUtil(root.right); // Update number of moves ans += Math.abs(l) + Math.abs(r); // Return number of moves to balance // current node return root.key + l + r - 1; } // Function to find the number of moves to // distribute all of the candies static int distributeCandy(Node root) { distributeCandyUtil(root); return ans; } // Driver program public static void main(String[] args) { /* 3 / \ 0 0 Let us create Binary Tree shown in above example */ Node root = newNode(3); root.left = newNode(0); root.right = newNode(0); System.out.println(distributeCandy(root)); }}// This code is contributed by Prerna Saini. |
Python3
# Python3 program to distribute candies# in a Binary Tree # Binary Tree Nodeclass Node: def __init__(self, key): self.key = key self.left = None self.right = None # Utility function to create a new nodedef newNode(key): temp = Node(key) return temp # Utility function to find the number of# moves to distribute all of the candiesdef distributeCandyUtil( root, ans): # Base Case if (root == None): return 0, ans; # Traverse left subtree l,ans = distributeCandyUtil(root.left, ans); # Traverse right subtree r,ans = distributeCandyUtil(root.right, ans); # Update number of moves ans += abs(l) + abs(r); # Return number of moves to balance # current node return root.key + l + r - 1, ans; # Function to find the number of moves to# distribute all of the candiesdef distributeCandy(root): ans = 0; tmp, ans = distributeCandyUtil(root, ans); return ans; # Driver programif __name__=='__main__': ''' 3 / \ 0 0 Let us create Binary Tree shown in above example ''' root = newNode(3); root.left = newNode(0); root.right = newNode(0); print(distributeCandy(root)) # This code is contributed by pratham76 |
C#
// C# program to distribute candies// in a Binary Treeusing System;class GFG { // Binary Tree Node public class Node { public int key; public Node left, right; } static int ans = 0; // Utility function to create a new node static Node newNode(int key) { Node temp = new Node(); temp.key = key; temp.left = null; temp.right = null; return (temp); } // Utility function to find the number of // moves to distribute all of the candies static int distributeCandyUtil(Node root) { // Base Case if (root == null) return 0; // Traverse left subtree int l = distributeCandyUtil(root.left); // Traverse right subtree int r = distributeCandyUtil(root.right); // Update number of moves ans += Math.Abs(l) + Math.Abs(r); // Return number of moves to balance // current node return root.key + l + r - 1; } // Function to find the number of moves to // distribute all of the candies static int distributeCandy(Node root) { distributeCandyUtil(root); return ans; } // Driver Code public static void Main(String[] args) { /* 3 / \ 0 0 Let us create Binary Tree shown in above example */ Node root = newNode(3); root.left = newNode(0); root.right = newNode(0); Console.WriteLine(distributeCandy(root)); }}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to distribute candies in a Binary Tree // Binary Tree Node class Node { constructor(key) { this.left = null; this.right = null; this.key = key; } } let ans = 0; // Utility function to create a new node function newNode(key) { let temp = new Node(key); return (temp); } // Utility function to find the number of // moves to distribute all of the candies function distributeCandyUtil(root) { // Base Case if (root == null) return 0; // Traverse left subtree let l = distributeCandyUtil(root.left); // Traverse right subtree let r = distributeCandyUtil(root.right); // Update number of moves ans += Math.abs(l) + Math.abs(r); // Return number of moves to balance // current node return root.key + l + r - 1; } // Function to find the number of moves to // distribute all of the candies function distributeCandy(root) { distributeCandyUtil(root); return ans; } /* 3 / \ 0 0 Let us create Binary Tree shown in above example */ let root = newNode(3); root.left = newNode(0); root.right = newNode(0); document.write(distributeCandy(root));</script> |
Output
2
Time Complexity: O(n) where n is the number of nodes in given Binary Tree.
Auxiliary Space: O(h) where h is the height of given Binary Tree due to Recursion
Iterative Solution:
Approach: At each node, some candies will come from the left and goes to the right or comes from the right and goes to left. At each case, moves will increase. So, for each node we will count number of required candies in the right child and in left child i.e (total number of node – total candies) for each child. It is possible that it might be less than 0 but in that case too it will counted as move because extra candies also has to travel through the root node.
Below is the implementation of the iterative approach:
C++
// C++ program to distribute// candies in a Binary Tree#include <bits/stdc++.h>using namespace std;// Binary Tree Nodestruct Node { int key; struct Node *left, *right;};// Utility function to create a new nodeNode* newNode(int key){ Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp);}int countinchild(Node* root){ // as node exists. if (root == NULL) return 0; int numberofnodes = 0; // to count total nodes. int sum = 0; // to count total candies present. queue<Node*> q; q.push(root); while (q.size() != 0) { Node* f = q.front(); q.pop(); numberofnodes++; sum += f->key; if (f->left) q.push(f->left); if (f->right) q.push(f->right); } // as either less than 0 or greater, it will be counted as // move as explained in the approach. return abs(numberofnodes - sum);}int distributeCandy(Node* root){ // moves will count for total no. of moves. int moves = 0; // as 0 node and 0 value. if (root == NULL) return 0; // as leaf node don't have to pass any candies. if (!root->left && !root->right) return 0; // queue to iterate on tree . queue<Node*> q; q.push(root); while (q.size() != 0) { Node* f = q.front(); q.pop(); // total pass from left child moves += countinchild(f->left); // total pass from right child moves += countinchild(f->right); if (f->left) q.push(f->left); if (f->right) q.push(f->right); } return moves;}// Driver programint main(){ /* 1 / \ 0 2 Let us create Binary Tree shown in above example */ Node* root = newNode(1); root->left = newNode(0); root->right = newNode(2); cout << distributeCandy(root); return 0;} |
Java
// Java program to distribute candies in a Binary Treeimport java.util.*;public class GFG{ static class Node { int key; Node left, right; Node(int item) { key = item; left = right = null; } } // Root of the Binary Tree static Node root; public GFG() { root = null; } // Utility function to create a new node static Node newNode(int key) { Node temp = new Node(key); return (temp); } static int countinchild(Node root) { // as node exists. if (root == null) return 0; int numberofnodes = 0; // to count total nodes. int sum = 0; // to count total candies present. Queue<Node> q = new LinkedList<>(); q.add(root); while (q.size() != 0) { Node f = (Node)q.peek(); q.remove(); numberofnodes++; sum += f.key; if (f.left != null) q.add(f.left); if (f.right != null) q.add(f.right); } // as either less than 0 or greater, it will be counted as // move as explained in the approach. return Math.abs(numberofnodes - sum); } static int distributeCandy(Node root) { // moves will count for total no. of moves. int moves = 0; // as 0 node and 0 value. if (root == null) return 0; // as leaf node don't have to pass any candies. if (root.left == null && root.right == null) return 0; // queue to iterate on tree . Queue<Node> q = new LinkedList<>(); q.add(root); while (q.size() != 0) { Node f = (Node)q.peek(); q.remove(); // total pass from left child moves += countinchild(f.left); // total pass from right child moves += countinchild(f.right); if (f.left != null) q.add(f.left); if (f.right != null) q.add(f.right); } return moves; } public static void main(String[] args) { /* 1 / \ 0 2 Let us create Binary Tree shown in above example */ GFG tree = new GFG(); tree.root = newNode(1); tree.root.left = newNode(0); tree.root.right = newNode(2); System.out.println(distributeCandy(tree.root)); }}// This code is contributed by divyeshrabadiyaa07. |
Python3
# Python3 program to distribute# candies in a Binary Tree # Binary Tree Nodeclass Node: def __init__(self, key): self.key = key self.left = None self.right = None # Utility function to create a new nodedef newNode(key): temp = Node(key) return temp def countinchild(root): # as node exists. if (root == None): return 0; numberofnodes = 0; # to count total nodes. sum = 0; # to count total candies present. q = [] q.append(root); while (len(q) != 0): f = q[0]; q.pop(0); numberofnodes += 1 sum += f.key; if (f.left): q.append(f.left); if (f.right): q.append(f.right); # as either less than 0 or greater, it will be counted as # move as explained in the approach. return abs(numberofnodes - sum);def distributeCandy(root): # moves will count for total no. of moves. moves = 0; # as 0 node and 0 value. if (root == None): return 0; # as leaf node don't have to pass any candies. if (not root.left and not root.right): return 0; # queue to iterate on tree . q = [] q.append(root); while (len(q) != 0): f = q[0]; q.pop(0); # total pass from left child moves += countinchild(f.left); # total pass from right child moves += countinchild(f.right); if (f.left): q.append(f.left); if (f.right): q.append(f.right); return moves;# Driver programif __name__=='__main__': ''' / 1 / \ 0 2 Let us create Binary Tree shown in above example ''' root = newNode(1); root.left = newNode(0); root.right = newNode(2); print(distributeCandy(root)) # This code is contributed by rutvik_56 |
C#
// C# program to distribute candies in a Binary Treeusing System;using System.Collections;using System.Collections.Generic;class Node { public int key; public Node left, right; public Node(int item) { key = item; left = right = null; }} public class GFG { // Root of the Binary Tree Node root; public GFG() { root = null; } // Utility function to create a new node static Node newNode(int key) { Node temp = new Node(key); return (temp); } static int countinchild(Node root) { // as node exists. if (root == null) return 0; int numberofnodes = 0; // to count total nodes. int sum = 0; // to count total candies present. Queue q = new Queue(); q.Enqueue(root); while (q.Count != 0) { Node f = (Node)q.Peek(); q.Dequeue(); numberofnodes++; sum += f.key; if (f.left != null) q.Enqueue(f.left); if (f.right != null) q.Enqueue(f.right); } // as either less than 0 or greater, it will be counted as // move as explained in the approach. return Math.Abs(numberofnodes - sum); } static int distributeCandy(Node root) { // moves will count for total no. of moves. int moves = 0; // as 0 node and 0 value. if (root == null) return 0; // as leaf node don't have to pass any candies. if (root.left == null && root.right == null) return 0; // queue to iterate on tree . Queue q = new Queue(); q.Enqueue(root); while (q.Count != 0) { Node f = (Node)q.Peek(); q.Dequeue(); // total pass from left child moves += countinchild(f.left); // total pass from right child moves += countinchild(f.right); if (f.left != null) q.Enqueue(f.left); if (f.right != null) q.Enqueue(f.right); } return moves; } static void Main() { /* 1 / \ 0 2 Let us create Binary Tree shown in above example */ GFG tree = new GFG(); tree.root = newNode(1); tree.root.left = newNode(0); tree.root.right = newNode(2); Console.Write(distributeCandy(tree.root)); }}// This code is contributed by decode2207. |
Javascript
<script> // Javascript program to distribute // candies in a Binary Tree class Node { constructor(key) { this.left = null; this.right = null; this.key = key; } } // Utility function to create a new node function newNode(key) { let temp = new Node(key); return (temp); } function countinchild(root) { // as node exists. if (root == null) return 0; let numberofnodes = 0; // to count total nodes. let sum = 0; // to count total candies present. let q = []; q.push(root); while (q.length != 0) { let f = q[0]; q.shift(); numberofnodes++; sum += f.key; if (f.left) q.push(f.left); if (f.right) q.push(f.right); } // as either less than 0 or greater, it will be counted as // move as explained in the approach. return Math.abs(numberofnodes - sum); } function distributeCandy(root) { // moves will count for total no. of moves. let moves = 0; // as 0 node and 0 value. if (root == null) return 0; // as leaf node don't have to pass any candies. if (root.left == null && root.right == null) return 0; // queue to iterate on tree . let q = []; q.push(root); while (q.length != 0) { let f = q[0]; q.shift(); // total pass from left child moves += countinchild(f.left); // total pass from right child moves += countinchild(f.right); if (f.left) q.push(f.left); if (f.right) q.push(f.right); } return moves; } /* 1 / \ 0 2 Let us create Binary Tree shown in above example */ let root = newNode(1); root.left = newNode(0); root.right = newNode(2); document.write(distributeCandy(root));</script> |
Output
2
Complexity Analysis:
- Time Complexity: O(N*N)
- Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
