Data Modelling & AI Data Structure & Algorithm

Count balanced nodes present in a binary tree

23 June 2025

0

Given a binary tree, the task is to count the number of balanced nodes in the given tree.

Balanced nodes of a binary tree are defined as the nodes which contains both left and right subtrees with their respective sum of node values equal.

Examples:

Input:

Output: 1
Explanation:
Only node 9 contains the left subtree sum = right subtree sum = 4
Therefore, the required output is 1.

Input:

                  7
                 / \
                4  10
              /  \     
            3    3
          / \     \
        0    0    -3
                  /
                 3

Output: 3

Approach: The idea is to recursively traverse every node of the given Binary Tree. For every node, calculate the sum of the nodes in the left and right subtree and check if the calculated sums are equal or not. If found to be true, increase count. Finally, print the count after complete traversal of the tree

Follow the steps below to solve the problem:

Initialize a variable say, res, to store the count of balanced nodes
Recursively calculate the sum of the left and right subtree for every node.
Check if the calculated sums are equal or not.
If found to be true, the current node is balanced. Therefore, increment res by 1
Finally, print the value of res after complete traversal of the tree.

Below is the implementation of the above approach:

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a
// Tree Node
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val)
    {
        data = val;
        left = right = NULL;
    }
};
 
// Function to get the sum of left
// subtree and right subtree
int Sum(Node* root, int& res)
{
    // Base case
    if (root == NULL) {
        return 0;
    }
 
    // Store the sum of
    // left subtree
    int leftSubSum
        = Sum(root->left, res);
 
    // Store the sum of
    // right subtree
    int rightSubSum
        = Sum(root->right, res);
 
    // Check if node is balanced or not
    if (root->left and root->right
        && leftSubSum == rightSubSum)
 
        // Increase count of
        // balanced nodes
        res += 1;
 
    // Return subtree sum
    return root->data + leftSubSum
           + rightSubSum;
}
 
// Driver Code
int main()
{
 
    /*
                   9
                 /  \
                2   4 
               / \   \
             -1   3   0
    */
 
    // Insert nodes in tree
    Node* root = new Node(9);
    root->left = new Node(2);
    root->left->left = new Node(-1);
    root->left->right = new Node(3);
    root->right = new Node(4);
    root->right->right = new Node(0);
 
    // Store the count of balanced nodes
    int res = 0;
    Sum(root, res);
    cout << res;
}

Java

// Java program to implement
// the above approach
class GFG{
     
static int res = 0;
   
// Structure of a
// Tree Node
static class Node 
{
  int data;
  Node left;
  Node right;
  Node(int val)
  {
    data = val;
    left = right = null;
  }
};
 
// Function to get the sum of left
// subtree and right subtree
static int Sum(Node root)
{
  // Base case
  if (root == null) 
  {
    return 0;
  }
 
  // Store the sum of
  // left subtree
  int leftSubSum = Sum(root.left);
 
  // Store the sum of
  // right subtree
  int rightSubSum = Sum(root.right);
 
  // Check if node is balanced or not
  if (root.left != null && root.right != null && 
      leftSubSum == rightSubSum)
 
    // Increase count of
    // balanced nodes
    res += 1;
 
  // Return subtree sum
  return root.data + leftSubSum + 
         rightSubSum;
}
 
// Driver Code
public static void main(String[] args)
{
  /*
                   9
                 /  \
                2   4 
               / \   \
             -1   3   0
    */
 
  // Insert nodes in tree
  Node root = new Node(9);
  root.left = new Node(2);
  root.left.left = new Node(-1);
  root.left.right = new Node(3);
  root.right = new Node(4);
  root.right.right = new Node(0);
 
  // Store the count of balanced nodes
  res = 0;
  Sum(root);
  System.out.print(res);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to implement
# the above approach
 
# Structure of a  Tree Node
class Node:
    def __init__(self, val):
         
        self.data = val
        self.left = None
        self.right = None
 
# Function to get the sum of left
# subtree and right subtree
def Sum(root):
 
    global res
 
    # Base case
    if (root == None):
        return 0
 
    # Store the sum of
    # left subtree
    leftSubSum = Sum(root.left)
 
    # Store the sum of
    # right subtree
    rightSubSum = Sum(root.right)
 
    # Check if node is balanced or not
    if (root.left and root.right and
       leftSubSum == rightSubSum):
 
        # Increase count of
        # balanced nodes
        res += 1
 
    # Return subtree sum
    return (root.data + leftSubSum +
                        rightSubSum)
 
# Driver Code
"""
                  9 
                 / \ 
                2   4  
               / \   \ 
             -1   3   0 
"""
# Insert nodes in tree
root = Node(9)
root.left = Node(2)
root.left.left = Node(-1)
root.left.right = Node(3)
root.right = Node(4)
root.right.right = Node(0)
 
# Store the count of balanced nodes 
global res
res = 0
Sum(root)
print(res)
 
# This code is contributed by Shivam Singh

C#

// C# program to implement
// the above approach
using System;
class GFG{
     
static int res = 0;
   
// Structure of a
// Tree Node
public class Node 
{
  public int data;
  public Node left;
  public Node right;
  public Node(int val)
  {
    data = val;
    left = right = null;
  }
};
 
// Function to get the sum of left
// subtree and right subtree
static int Sum(Node root)
{
  // Base case
  if (root == null) 
  {
    return 0;
  }
 
  // Store the sum of
  // left subtree
  int leftSubSum = Sum(root.left);
 
  // Store the sum of
  // right subtree
  int rightSubSum = Sum(root.right);
 
  // Check if node is balanced or not
  if (root.left != null && root.right != null && 
      leftSubSum == rightSubSum)
 
    // Increase count of
    // balanced nodes
    res += 1;
 
  // Return subtree sum
  return root.data + leftSubSum + 
         rightSubSum;
}
 
// Driver Code
public static void Main(String[] args)
{
  /*
                   9
                 /  \
                2   4 
               / \   \
             -1   3   0
    */
 
  // Insert nodes in tree
  Node root = new Node(9);
  root.left = new Node(2);
  root.left.left = new Node(-1);
  root.left.right = new Node(3);
  root.right = new Node(4);
  root.right.right = new Node(0);
 
  // Store the count of balanced nodes
  res = 0;
  Sum(root);
  Console.Write(res);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
    // JavaScript program for the above approach
     
    let res = 0;
    
    // Structure of a Tree Node
    class Node
    {
        constructor(val) {
           this.left = null;
           this.right = null;
           this.data = val;
        }
    }
 
    // Function to get the sum of left
    // subtree and right subtree
    function Sum(root)
    {
      // Base case
      if (root == null)
      {
        return 0;
      }
 
      // Store the sum of
      // left subtree
      let leftSubSum = Sum(root.left);
 
      // Store the sum of
      // right subtree
      let rightSubSum = Sum(root.right);
 
      // Check if node is balanced or not
      if (root.left != null && root.right != null &&
          leftSubSum == rightSubSum)
 
        // Increase count of
        // balanced nodes
        res += 1;
 
      // Return subtree sum
      return root.data + leftSubSum +
             rightSubSum;
    }
     
    /*
                   9
                 /  \
                2   4
               / \   \
             -1   3   0
    */
  
    // Insert nodes in tree
    let root = new Node(9);
    root.left = new Node(2);
    root.left.left = new Node(-1);
    root.left.right = new Node(3);
    root.right = new Node(4);
    root.right.right = new Node(0);
 
    // Store the count of balanced nodes
    res = 0;
    Sum(root);
    document.write(res);
 
</script>

Output:

Time Complexity: O(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!

Count balanced nodes present in a binary tree

C++

Java

Python3

C#

Javascript

Smarter Retrieval for RAG: Late Chunking with Jina Embeddings v2 and Milvus

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US