Distribute candies in a Binary Tree

Last Updated : 8 Oct, 2025

Given the root of a binary tree with n nodes, where each node contains a certain number of candies, and the total number of candies across all nodes is n.

In one move, we can select two adjacent nodes and transfer one candy from one node to the other. The transfer can occur between a parent and child in either direction.
Find the minimum number of moves required to ensure that every node in the tree has exactly one candy.

Examples:

Input:

Output: 6
Explanation:
Move 1 candy from root to root->left node
Move 1 candy from root to root->right node
Move 1 candy from root->right node to root->right->left node
Move 1 candy from root to root->right child
Move 1 candy from root->right node to root->right->right node
Move 1 candy from root to root->right node
So, total 6 moves required.
Input:

Output: 4
Explanation:
Move 1 candy from root to left child
Move 1 candy from root->right->left node to root->right node
Move 1 candy from root->right node to root->right->right node
Move 1 candy from root->right->left node to root->right node
So, total 4 moves required.

Try it on GfG Practice

Table of Content

[Expected Approach - 1] Using Recursion - O(n) Time and O(h) Space
[Expected Approach - 2] Using Iteration - O(n) Time and O(n) Space

[Expected Approach - 1] Using Recursion - O(n) Time and O(h) Space

The idea is to use recursion 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 then we should push a candy from its parent onto the node.
If the node has more than 1 candy. ex. 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(numCandies - 1). Once a node is balanced, we never have to consider this node again in the rest of our calculation.

C++

#include <iostream>
using namespace std;

// Node Structure
class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int x) {
        data = x;
        left = right = nullptr;
    }
};

// function to find the number of
// moves to distribute all of the candies
int distCandyUtil(Node* root, int& ans) {
  
    if (root == nullptr)
        return 0;

    // Traverse left subtree
    int l = distCandyUtil(root->left, ans);

    // Traverse right subtree
    int r = distCandyUtil(root->right, ans);

    ans += abs(l) + abs(r);

    // Return number of moves to balance
    // current node
    return root->data + l + r - 1;
}

// Function to find the number of moves
int distCandy(Node* root) {
    int ans = 0;
    distCandyUtil(root, ans);
    return ans;
}

int main() {
    
     
   // Representation of given Binary Tree
//        5
//       / \
//      0   0
//         / \
//        0   0
    Node* root = new Node(5);
    root->left = new Node(0);
    root->right = new Node(0);
    root->right->left = new Node(0);
    root->right->right = new Node(0);

    cout << distCandy(root);

    return 0;
}

Java

// Node Structure
class Node {
    public int data;
    public Node left, right;

    public Node(int x) {
        data = x;
        left = right = null;
    }
}

class GFG {
  
    //function to find the number of
    // moves to distribute all of the candies
    static int distCandyUtil(Node root, int[] ans) {

        if (root == null)
            return 0;

        // Traverse left subtree
        int l = distCandyUtil(root.left, ans);

        // Traverse right subtree
        int r = distCandyUtil(root.right, ans);

        ans[0] += Math.abs(l) + Math.abs(r);

        // Return number of moves to balance
        // current node
        return root.data + l + r - 1;
    }

    // Function to find the number of moves 
    static int distCandy(Node root) {
        int[] ans = new int[1];

        distCandyUtil(root, ans);

        return ans[0];
    }

    public static void main(String[] args) {
        
        // Representation of given Binary Tree
//        5
//       / \
//      0   0
//         / \
//        0   0
        Node root = new Node(5);
        root.left = new Node(0);
        root.right = new Node(0);
        root.right.left = new Node(0);
        root.right.right = new Node(0);

        System.out.println(distCandy(root));
    }
}

Python

# Node Structure
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

# function to find the number of
# moves to distribute all of the candies
def distCandyUtil(root, ans):
    
    if root is None:
        return 0

    # Traverse left subtree
    l = distCandyUtil(root.left, ans)

    # Traverse right subtree
    r = distCandyUtil(root.right, ans)

    ans[0] += abs(l) + abs(r)

    # Return number of moves to balance
    # current node
    return root.data + l + r - 1

# Function to find the number of moves 
def distCandy(root):
    ans = [0]
    
    distCandyUtil(root, ans)
    
    return ans[0]

if __name__ == "__main__":
    
       #  Representation of given Binary Tree
    #         5
    #        / \
    #       0   0
    #          / \
    #         0   0
    root = Node(5)
    root.left = Node(0)
    root.right = Node(0)
    root.right.left = Node(0)
    root.right.right = Node(0)

    print(distCandy(root))

C#

using System;

// Node Structure
class Node {
    public int data;
    public Node left, right;

    public Node(int x) {
        data = x;
        left = right = null;
    }
}

// function to find the number of
// moves to distribute all of the candies
class GFG {
    static int distCandyUtil(Node root, ref int ans) {

        if (root == null)
            return 0;

        // Traverse left subtree
        int l = distCandyUtil(root.left, ref ans);

        // Traverse right subtree
        int r = distCandyUtil(root.right, ref ans);

        ans += Math.Abs(l) + Math.Abs(r);

        // Return number of moves to balance
        // current node
        return root.data + l + r - 1;
    }

    // Function to find the number of moves 
    static int distCandy(Node root) {
        int ans = 0;
        distCandyUtil(root, ref ans);
        return ans;
    }
  
    static void Main(string[] args) {
        
        // Representation of given Binary Tree
        //        5
        //       / \
        //      0   0
        //         / \
        //        0   0
        Node root = new Node(5);
        root.left = new Node(0);
        root.right = new Node(0);
        root.right.left = new Node(0);
        root.right.right = new Node(0);
        Console.WriteLine(distCandy(root));
    }
}

JavaScript

// Node Structure
class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}

// function to find the number of
// moves to distribute all of the candies
function distCandyUtil(root, ans) {

    if (root === null)
        return 0;

    // Traverse left subtree
    let l = distCandyUtil(root.left, ans);

    // Traverse right subtree
    let r = distCandyUtil(root.right, ans);

    ans.moves += Math.abs(l) + Math.abs(r);

    // Return number of moves to balance
    // current node
    return root.data + l + r - 1;
}

// Function to find the number of moves 
function distCandy(root) {
    let ans = { moves: 0 };
    
    distCandyUtil(root, ans);
    
    return ans.moves;
}

// Driver Code

  // Representation of given Binary Tree
//        5
//       / \
//      0   0
//         / \
//        0   0
let root = new Node(5);
root.left = new Node(0);
root.right = new Node(0);
root.right.left = new Node(0);
root.right.right = new Node(0);


console.log(distCandy(root));

Output

[Expected Approach - 2] Using Iteration - O(n) Time and O(n) Space

At each node, some candies will come from the left and goes to the right or vice versa. 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.

Steps:

We use a stack to traverse the tree in post-order without recursion.
Track each node’s state to ensure children are processed before the parent.
We use a map to store excess candies at each node: excess = nodeCandies + leftExcess + rightExcess - 1.
Count moves as abs(leftExcess) + abs(rightExcess).
Pass the node’s excess to its parent.
Repeat until the root is processed; total moves give the minimum required.

C++

#include <iostream>
#include<stack>
#include<unordered_map>
using namespace std;

// Node Structure
class Node {
public:

    int data;
    Node* left;
    Node* right;
  
    Node(int x) {
        data = x;
        left = right = nullptr;
    }
};

// Function to find the number of moves 
int distCandy(Node* root) {

    if (root == nullptr) return 0;
    int ans = 0;

    stack<pair<Node*, int>> stk;

    unordered_map<Node*, int> balance;

    // Push root node into the stack 
    // with state 0 (not processed)
    stk.push({root, 0});

    while (!stk.empty()) {

        // Get the top node and its state 
        // from the stack
        auto curr = stk.top();
        auto node = curr.first;
        auto state = curr.second;
        stk.pop();

        if (node == nullptr) continue;

        // If state is 0, push node back with 
        // state 1 (post-processing)
        if (state == 0) {

            // Push current node back with 
            // state 1 for post-order processing
            stk.push({node, 1});

            stk.push({node->left, 0});

            stk.push({node->right, 0});

        } 
        else {

            int leftBalance = balance[node->left];

            int rightBalance = balance[node->right];

            // Add moves required for left and right subtrees
            ans += abs(leftBalance) + abs(rightBalance);

            // Calculate current node's balance: (candies - 1)
            balance[node] 
              = node->data + leftBalance + rightBalance - 1;
        }
    }
  
    return ans;
}

int main() {
    
   // Representation of given Binary Tree
//        5
//       / \
//      0   0
//         / \
//        0   0
    Node* root = new Node(5);
    root->left = new Node(0);
    root->right = new Node(0);
    root->right->left = new Node(0);
    root->right->right = new Node(0);
    cout << distCandy(root);

    return 0;
}

Java

import java.util.Stack;
import java.util.HashMap;

// Node Structure
class Node {

    int data;
    Node left;
    Node right;
  
    Node(int x) {
        data = x;
        left = right = null;
    }
}

class Pair<K, V> {

    private K key;
    private V value;
  
    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    // Method to get the key
    public K getKey() {
        return key;
    }

    // Method to get the value
    public V getValue() {
        return value;
    }

    // Method to set the key
    public void setKey(K key) {
        this.key = key;
    }

    // Method to set the value
    public void setValue(V value) {
        this.value = value;
    }
}

// Function to find the number of moves 
class GFG {

    static int distCandy(Node root) {

        if (root == null) return 0;
        int ans = 0;

        Stack<Pair<Node, Integer>> stk = new Stack<>();

        HashMap<Node, Integer> balance = new HashMap<>();

        // Push root node into the stack 
        // with state 0 (not processed)
        stk.push(new Pair<>(root, 0));

        while (!stk.isEmpty()) {

            // Get the top node and its state 
            // from the stack
            Pair<Node, Integer> curr = stk.pop();
            Node node = curr.getKey();
            int state = curr.getValue();

            if (node == null) continue;

            // If state is 0, push node back with 
            // state 1 (post-processing)
            if (state == 0) {

                // Push current node back with 
                // state 1 for post-order processing
                stk.push(new Pair<>(node, 1));

                stk.push(new Pair<>(node.left, 0));

                stk.push(new Pair<>(node.right, 0));

            } 
            else {

                int leftBalance 
                         = balance.getOrDefault(node.left, 0);

                int rightBalance 
                         = balance.getOrDefault(node.right, 0);

                // Add moves required for left and right subtrees
                ans += Math.abs(leftBalance) 
                            + Math.abs(rightBalance);

                // Calculate current node's balance: (candies - 1)
                balance.put(node, node.data 
                            + leftBalance + rightBalance - 1);
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        
      // Representation of given Binary Tree
//        5
//       / \
//      0   0
//         / \
//        0   0
       Node root = new Node(5);
        root.left = new Node(0);
        root.right = new Node(0);
        root.right.left = new Node(0);
        root.right.right = new Node(0);
        System.out.println(distCandy(root));
    }
}

Python

# Node Structure
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

# Function to find the number of moves 
def distCandy(root):
    
    if root is None:
        return 0

    ans = 0

    stk = []

    # Dictionary to store balance of
    # candies at each node
    balance = {}

    # Push root node into the stack 
    # with state 0 (not processed)
    stk.append((root, 0))

    while stk:

        # Get the top node and its state 
        # from the stack
        curr = stk.pop()
        node = curr[0]
        state = curr[1]

        if node is None:
            continue

        # If state is 0, push node back with 
        # state 1 (post-processing)
        if state == 0:

            # Push current node back with 
            # state 1 for post-order processing
            stk.append((node, 1))

            stk.append((node.left, 0))

            stk.append((node.right, 0))

        else:

            leftBalance = balance.get(node.left, 0)

            rightBalance = balance.get(node.right, 0)

            # Add moves required for left and right subtrees
            ans += abs(leftBalance) + abs(rightBalance)

            # Calculate current node's balance: (candies - 1)
            balance[node] = node.data + leftBalance + rightBalance - 1

    return ans

if __name__ == "__main__":
    
    #  Representation of given Binary Tree
#         5
#        / \
#       0   0
#          / \
#         0   0
    root = Node(5)
    root.left = Node(0)
    root.right = Node(0)
    root.right.left = Node(0)
    root.right.right = Node(0)
    print(distCandy(root))

C#

using System;
using System.Collections.Generic;

// Node Structure
class Node {
    public int data;
    public Node left;
    public Node right;

    public Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GFG {
  
    // Function to find the number of moves 
    static int distCandy(Node root) {

        if (root == null) return 0;

        int ans = 0;

        Stack<(Node, int)> stk
                   = new Stack<(Node, int)>();

        // Dictionary to store balance of 
      	// candies at each node
        Dictionary<Node, int> balance
                   = new Dictionary<Node, int>();

        // Push root node into the stack 
        // with state 0 (not processed)
        stk.Push((root, 0));

        while (stk.Count > 0) {

            // Get the top node and its state 
            // from the stack
            var curr = stk.Pop();
            var node = curr.Item1;
            var state = curr.Item2;

            if (node == null) continue;

            // If state is 0, push node back with 
            // state 1 (post-processing)
            if (state == 0) {

                // Push current node back with 
                // state 1 for post-order processing
                stk.Push((node, 1));

                stk.Push((node.left, 0));

                stk.Push((node.right, 0));

            } 
            else {

                int leftBalance = (node.left != null 
                            && balance.ContainsKey(node.left)) 
                            ? balance[node.left] : 0;

                int rightBalance = (node.right != null
                            && balance.ContainsKey(node.right)) 
                             ? balance[node.right] : 0;

                // Add moves required for left and right subtrees
                ans += Math.Abs(leftBalance)
                              + Math.Abs(rightBalance);

                // Calculate current node's balance: (candies - 1)
                balance[node] 
                  = node.data + leftBalance + rightBalance - 1;
            }
        }
      
        return ans;
    }

    static void Main() {

         // Representation of given Binary Tree
//        5
//       / \
//      0   0
//         / \
//        0   0
        Node root = new Node(5);
        root.left = new Node(0);
        root.right = new Node(0);
        root.right.left = new Node(0);
        root.right.right = new Node(0);

        Console.WriteLine(distCandy(root));
    }
}

JavaScript

// Node Structure
class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}

// Function to find the number of moves 
function distCandy(root) {

    if (root === null) return 0;

    let ans = 0;

    const stk = [];

    // Map to store balance of candies
    // at each node
    const balance = new Map();

    // Push root node into the stack 
    // with state 0 (not processed)
    stk.push([root, 0]);

    while (stk.length > 0) {

        // Get the top node and its state 
        // from the stack
        const [node, state] = stk.pop();

        if (node === null) continue;

        // If state is 0, push node back with 
        // state 1 (post-processing)
        if (state === 0) {

            // Push current node back with 
            // state 1 for post-order processing
            stk.push([node, 1]);

            stk.push([node.left, 0]);
            stk.push([node.right, 0]);

        } 
        else {

            const leftBalance = node.left && balance.has(node.left) 
                ? balance.get(node.left) 
                : 0;

            const rightBalance = node.right && balance.has(node.right) 
                ? balance.get(node.right) 
                : 0;

            // Add moves required for left and right subtrees
            ans += Math.abs(leftBalance) + Math.abs(rightBalance);

            // Calculate current node's balance: (candies - 1)
            balance.set(node, node.data + leftBalance + rightBalance - 1);
        }
    }

    return ans;
}

// Driver Code

   // Representation of given Binary Tree
//        5
//       / \
//      0   0
//         / \
//        0   0
let root = new Node(5);
root.left = new Node(0);
root.right = new Node(0);
root.right.left = new Node(0);
root.right.right = new Node(0);

console.log(distCandy(root));

Output

Comment

Article Tags:

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem