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:
9 / \ 2 4 / \ \ -1 3 0Output: 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 / 3Output: 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 Nodestruct 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 subtreeint 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 Codeint 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 approachclass GFG{ static int res = 0; // Structure of a// Tree Nodestatic 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 subtreestatic 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 Codepublic 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 Nodeclass Node: def __init__(self, val): self.data = val self.left = None self.right = None# Function to get the sum of left# subtree and right subtreedef 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 treeroot = 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 resres = 0Sum(root)print(res)# This code is contributed by Shivam Singh |
C#
// C# program to implement// the above approachusing System;class GFG{ static int res = 0; // Structure of a// Tree Nodepublic 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 subtreestatic 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 Codepublic 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:
1
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
