Posted on by Kalkicode
Code Recursion

# Count balanced nodes present in a binary tree

The problem at hand involves counting the number of balanced nodes in a binary tree. A binary tree is a hierarchical structure in which each node has at most two children, often referred to as the left child and the right child. A balanced node is one where the sum of the values of its left and right subtrees is equal. In this problem, we are required to design a program in C that counts the number of balanced nodes present in a given binary tree.

## Problem Statement

Given a binary tree, the task is to count the number of balanced nodes. A balanced node is defined as a node in the binary tree where the sum of the values in its left and right subtrees is equal.

## Example

Consider the binary tree described in the code comments:

``````
4
/   \
-4     7
/ \     \
2   3     12
/   / \    / \
1  -1  -1  5   7
/            \
-2              2

``````

In this tree, the nodes with values -4, 3, and 12 are balanced nodes since the sum of the values in their left and right subtrees is equal. Therefore, the output of the program will be:

``Balanced Node: 3``

## Idea to Solve

To solve this problem, we can follow these steps:

1. Create structures for the binary tree and its nodes to organize and store the tree's data.
2. Implement functions to create a new binary tree and to create new binary tree nodes with given values.
3. Define a recursive function to traverse the binary tree and count the balanced nodes. This function should calculate the sum of values in the left and right subtrees of each node and compare them to determine if the node is balanced.
4. Initialize a count variable and call the recursive function with the root node to count the number of balanced nodes.
5. Print the count of balanced nodes as the final output.

## Algorithm

1. Define structures `TreeNode` and `BinaryTree` to represent nodes and the binary tree, respectively.
2. Implement functions `newTree()` and `getNode(int data)` to create a new binary tree and binary tree nodes.
3. Define the `balancedNodes(struct TreeNode *node, int *count)` function to:
• Return 0 if the node is `NULL`.
• Recursively calculate the sum of left and right subtrees' values and compare them.
• If the node is balanced, increment the count.
• Return the sum of the values in the node and its subtrees.
4. In the `main()` function:
• Create a new binary tree.
• Construct the binary tree as described in the example.
• Initialize a count variable.
• Call `balancedNodes()` with the root node and the count variable.
• Print the count of balanced nodes.

## Code Solution

``````// C program for
// Count balanced nodes present in a binary tree
#include <stdio.h>

#include <stdlib.h>

// Tree Node
struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};
// Binary Tree
struct BinaryTree
{
struct TreeNode *root;
};
// Create new tree
struct BinaryTree *newTree()
{
// Create dynamic node
struct BinaryTree *tree = (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
//return new tree
return tree;
}
// This is creates and returns the new binary tree node
struct TreeNode *getNode(int data)
{
// Create dynamic node
struct TreeNode *new_node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (new_node != NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return new_node;
}
// This is Recursively find sum of left and right subtree
// and count balanced node.
int balancedNodes(struct TreeNode *node, int *count)
{
if (node == NULL)
{
return 0;
}
// Count sum of left subtree
int a = balancedNodes(node->left, count);
// Count sum of right subtree
int b = balancedNodes(node->right, count);
if (node->left != NULL && node->right != NULL && a == b)
{
// When left and right subtree not null
// And their sum are equal
*count += 1;
}
// Sum of all left subtree right subtree and current node
return a + b + node->data;
}
int main(int argc, char
const *argv[])
{
struct BinaryTree *tree = newTree();
/*
4
/   \
-4     7
/ \     \
2   3     12
/   / \    / \
1  -1  -1  5   7
/            \
-2              2

-----------------
Constructing binary tree

*/
tree->root = getNode(4);
tree->root->left = getNode(-4);
tree->root->left->right = getNode(3);
tree->root->left->right->left = getNode(-1);
tree->root->left->right->right = getNode(-1);
tree->root->left->left = getNode(2);
tree->root->left->left->left = getNode(1);
tree->root->left->left->left->left = getNode(-2);
tree->root->right = getNode(7);
tree->root->right->right = getNode(12);
tree->root->right->right->right = getNode(7);
tree->root->right->right->left = getNode(5);
tree->root->right->right->left->right = getNode(2);
// balanced node counter
int count = 0;
// Test
// Here [-4,3,12 ] is resultant node
// Because their left and right subtree sum is equal
balancedNodes(tree->root, & count);
// Print number of balanced node
printf("\n Balanced Node : %d \n", count);
return 0;
}``````

#### input

`` Balanced Node : 3``
``````// Java program for
// Count balanced nodes present in a binary tree
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public int count;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
this.count = 0;
}
// This is Recursively find sum of left and right subtree
// and count balanced node.
public int countBalancedNodes(TreeNode node)
{
if (node == null)
{
return 0;
}
// Count sum of left subtree
int a = countBalancedNodes(node.left);
// Count sum of right subtree
int b = countBalancedNodes(node.right);
if (node.left != null && node.right != null && a == b)
{
// When left and right subtree not null
// And their sum are equal
this.count += 1;
}
// Sum of all left subtree right subtree and current node
return a + b + node.data;
}
public void balancedNodes()
{
if (this.root == null)
{
System.out.print("\n Empty Tree \n");
}
this.count = 0;
countBalancedNodes(this.root);
System.out.print("\n Balanced Node : " + this.count + " \n");
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
4
/   \
-4     7
/ \     \
2   3     12
/   / \    / \
1  -1  -1  5   7
/            \
-2              2

-----------------
Constructing binary tree

*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(-4);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(-1);
tree.root.left.right.right = new TreeNode(-1);
tree.root.left.left = new TreeNode(2);
tree.root.left.left.left = new TreeNode(1);
tree.root.left.left.left.left = new TreeNode(-2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(2);
// Test
// Here [-4,3,12 ] is resultant node
// Because their left and right subtree sum is equal
tree.balancedNodes();
}
}``````

#### input

`` Balanced Node : 3``
``````// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Count balanced nodes present in a binary tree

// Binary Tree node
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public: TreeNode *root;
int count;
BinaryTree()
{
this->root = NULL;
this->count = 0;
}
// This is Recursively find sum of left and right subtree
// and count balanced node.
int countBalancedNodes(TreeNode *node)
{
if (node == NULL)
{
return 0;
}
// Count sum of left subtree
int a = this->countBalancedNodes(node->left);
// Count sum of right subtree
int b = this->countBalancedNodes(node->right);
if (node->left != NULL && node->right != NULL && a == b)
{
// When left and right subtree not null
// And their sum are equal
this->count += 1;
}
// Sum of all left subtree right subtree and current node
return a + b + node->data;
}
void balancedNodes()
{
if (this->root == NULL)
{
cout << "\n Empty Tree \n";
}
this->count = 0;
this->countBalancedNodes(this->root);
cout << "\n Balanced Node : " << this->count << " \n";
}
};
int main()
{
BinaryTree *tree = new BinaryTree();
/*
4
/   \
-4     7
/ \     \
2   3     12
/   / \    / \
1  -1  -1  5   7
/            \
-2              2
-----------------
Constructing binary tree
*/
tree->root = new TreeNode(4);
tree->root->left = new TreeNode(-4);
tree->root->left->right = new TreeNode(3);
tree->root->left->right->left = new TreeNode(-1);
tree->root->left->right->right = new TreeNode(-1);
tree->root->left->left = new TreeNode(2);
tree->root->left->left->left = new TreeNode(1);
tree->root->left->left->left->left = new TreeNode(-2);
tree->root->right = new TreeNode(7);
tree->root->right->right = new TreeNode(12);
tree->root->right->right->right = new TreeNode(7);
tree->root->right->right->left = new TreeNode(5);
tree->root->right->right->left->right = new TreeNode(2);
// Test
// Here [-4,3,12 ] is resultant node
// Because their left and right subtree sum is equal
tree->balancedNodes();
return 0;
}``````

#### input

`` Balanced Node : 3``
``````// Include namespace system
using System;
// Csharp program for
// Count balanced nodes present in a binary tree

// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public int count;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
this.count = 0;
}
// This is Recursively find sum of left and right subtree
// and count balanced node.
public int countBalancedNodes(TreeNode node)
{
if (node == null)
{
return 0;
}
// Count sum of left subtree
int a = this.countBalancedNodes(node.left);
// Count sum of right subtree
int b = this.countBalancedNodes(node.right);
if (node.left != null && node.right != null && a == b)
{
// When left and right subtree not null
// And their sum are equal
this.count += 1;
}
// Sum of all left subtree right subtree and current node
return a + b + node.data;
}
public void balancedNodes()
{
if (this.root == null)
{
Console.Write("\n Empty Tree \n");
}
this.count = 0;
this.countBalancedNodes(this.root);
Console.Write("\n Balanced Node : " + this.count + " \n");
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
4
/   \
-4     7
/ \     \
2   3     12
/   / \    / \
1  -1  -1  5   7
/            \
-2              2
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(-4);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(-1);
tree.root.left.right.right = new TreeNode(-1);
tree.root.left.left = new TreeNode(2);
tree.root.left.left.left = new TreeNode(1);
tree.root.left.left.left.left = new TreeNode(-2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(2);
// Test
// Here [-4,3,12 ] is resultant node
// Because their left and right subtree sum is equal
tree.balancedNodes();
}
}``````

#### input

`` Balanced Node : 3``
``````<?php
// Php program for
// Count balanced nodes present in a binary tree

// Binary Tree node
class TreeNode
{
public \$data;
public \$left;
public \$right;
public	function __construct(\$data)
{
// Set node value
\$this->data = \$data;
\$this->left = NULL;
\$this->right = NULL;
}
}
class BinaryTree
{
public \$root;
public \$count;
public	function __construct()
{
\$this->root = NULL;
\$this->count = 0;
}
// This is Recursively find sum of left and right subtree
// and count balanced node.
public	function countBalancedNodes(\$node)
{
if (\$node == NULL)
{
return 0;
}
// Count sum of left subtree
\$a = \$this->countBalancedNodes(\$node->left);
// Count sum of right subtree
\$b = \$this->countBalancedNodes(\$node->right);
if (\$node->left != NULL && \$node->right != NULL && \$a == \$b)
{
// When left and right subtree not null
// And their sum are equal
\$this->count += 1;
}
// Sum of all left subtree right subtree and current node
return \$a + \$b + \$node->data;
}
public	function balancedNodes()
{
if (\$this->root == NULL)
{
echo("\n Empty Tree \n");
}
\$this->count = 0;
\$this->countBalancedNodes(\$this->root);
echo("\n Balanced Node : ".\$this->count.
" \n");
}
}

function main()
{
\$tree = new BinaryTree();
/*
4
/   \
-4     7
/ \     \
2   3     12
/   / \    / \
1  -1  -1  5   7
/            \
-2              2
-----------------
Constructing binary tree
*/
\$tree->root = new TreeNode(4);
\$tree->root->left = new TreeNode(-4);
\$tree->root->left->right = new TreeNode(3);
\$tree->root->left->right->left = new TreeNode(-1);
\$tree->root->left->right->right = new TreeNode(-1);
\$tree->root->left->left = new TreeNode(2);
\$tree->root->left->left->left = new TreeNode(1);
\$tree->root->left->left->left->left = new TreeNode(-2);
\$tree->root->right = new TreeNode(7);
\$tree->root->right->right = new TreeNode(12);
\$tree->root->right->right->right = new TreeNode(7);
\$tree->root->right->right->left = new TreeNode(5);
\$tree->root->right->right->left->right = new TreeNode(2);
// Test
// Here [-4,3,12 ] is resultant node
// Because their left and right subtree sum is equal
\$tree->balancedNodes();
}
main();``````

#### input

`` Balanced Node : 3``
``````// Node JS program for
// Count balanced nodes present in a binary tree

// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
this.count = 0;
}
// This is Recursively find sum of left and right subtree
// and count balanced node.
countBalancedNodes(node)
{
if (node == null)
{
return 0;
}
// Count sum of left subtree
var a = this.countBalancedNodes(node.left);
// Count sum of right subtree
var b = this.countBalancedNodes(node.right);
if (node.left != null && node.right != null && a == b)
{
// When left and right subtree not null
// And their sum are equal
this.count += 1;
}
// Sum of all left subtree right subtree and current node
return a + b + node.data;
}
balancedNodes()
{
if (this.root == null)
{
process.stdout.write("\n Empty Tree \n");
}
this.count = 0;
this.countBalancedNodes(this.root);
process.stdout.write("\n Balanced Node : " + this.count + " \n");
}
}

function main()
{
var tree = new BinaryTree();
/*
4
/   \
-4     7
/ \     \
2   3     12
/   / \    / \
1  -1  -1  5   7
/            \
-2              2
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(-4);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(-1);
tree.root.left.right.right = new TreeNode(-1);
tree.root.left.left = new TreeNode(2);
tree.root.left.left.left = new TreeNode(1);
tree.root.left.left.left.left = new TreeNode(-2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(2);
// Test
// Here [-4,3,12 ] is resultant node
// Because their left and right subtree sum is equal
tree.balancedNodes();
}
main();``````

#### input

`` Balanced Node : 3``
``````#  Python 3 program for
#  Count balanced nodes present in a binary tree

#  Binary Tree node
class TreeNode :
def __init__(self, data) :
#  Set node value
self.data = data
self.left = None
self.right = None

class BinaryTree :
def __init__(self) :
self.root = None
self.count = 0

#  This is Recursively find sum of left and right subtree
#  and count balanced node.
def countBalancedNodes(self, node) :
if (node == None) :
return 0

#  Count sum of left subtree
a = self.countBalancedNodes(node.left)
#  Count sum of right subtree
b = self.countBalancedNodes(node.right)
if (node.left != None and node.right != None and a == b) :
#  When left and right subtree not null
#  And their sum are equal
self.count += 1

#  Sum of all left subtree right subtree and current node
return a + b + node.data

def balancedNodes(self) :
if (self.root == None) :
print("\n Empty Tree ")

self.count = 0
self.countBalancedNodes(self.root)
print("\n Balanced Node : ", self.count ," ")

def main() :
tree = BinaryTree()
#             4
#           /   \
#         -4     7
#         / \     \
#        2   3     12
#       /   / \    / \
#      1  -1  -1  5   7
#     /            \
#   -2              2
#    -----------------
#    Constructing binary tree
tree.root = TreeNode(4)
tree.root.left = TreeNode(-4)
tree.root.left.right = TreeNode(3)
tree.root.left.right.left = TreeNode(-1)
tree.root.left.right.right = TreeNode(-1)
tree.root.left.left = TreeNode(2)
tree.root.left.left.left = TreeNode(1)
tree.root.left.left.left.left = TreeNode(-2)
tree.root.right = TreeNode(7)
tree.root.right.right = TreeNode(12)
tree.root.right.right.right = TreeNode(7)
tree.root.right.right.left = TreeNode(5)
tree.root.right.right.left.right = TreeNode(2)
#  Test
#  Here [-4,3,12 ] is resultant node
#  Because their left and right subtree sum is equal
tree.balancedNodes()

if __name__ == "__main__": main()``````

#### input

`` Balanced Node :  3``
``````#  Ruby program for
#  Count balanced nodes present in a binary tree

#  Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :data, :left, :right
def initialize(data)
#  Set node value
self.data = data
self.left = nil
self.right = nil
end

end

class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_accessor :root, :count
def initialize()
self.root = nil
self.count = 0
end

#  This is Recursively find sum of left and right subtree
#  and count balanced node.
def countBalancedNodes(node)
if (node == nil)
return 0
end

#  Count sum of left subtree
a = self.countBalancedNodes(node.left)
#  Count sum of right subtree
b = self.countBalancedNodes(node.right)
if (node.left != nil && node.right != nil && a == b)
#  When left and right subtree not null
#  And their sum are equal
self.count += 1
end

#  Sum of all left subtree right subtree and current node
return a + b + node.data
end

def balancedNodes()
if (self.root == nil)
print("\n Empty Tree \n")
end

self.count = 0
self.countBalancedNodes(self.root)
print("\n Balanced Node : ", self.count ," \n")
end

end

def main()
tree = BinaryTree.new()
#             4
#           /   \
#         -4     7
#         / \     \
#        2   3     12
#       /   / \    / \
#      1  -1  -1  5   7
#     /            \
#   -2              2
#    -----------------
#    Constructing binary tree
tree.root = TreeNode.new(4)
tree.root.left = TreeNode.new(-4)
tree.root.left.right = TreeNode.new(3)
tree.root.left.right.left = TreeNode.new(-1)
tree.root.left.right.right = TreeNode.new(-1)
tree.root.left.left = TreeNode.new(2)
tree.root.left.left.left = TreeNode.new(1)
tree.root.left.left.left.left = TreeNode.new(-2)
tree.root.right = TreeNode.new(7)
tree.root.right.right = TreeNode.new(12)
tree.root.right.right.right = TreeNode.new(7)
tree.root.right.right.left = TreeNode.new(5)
tree.root.right.right.left.right = TreeNode.new(2)
#  Test
#  Here [-4,3,12 ] is resultant node
#  Because their left and right subtree sum is equal
tree.balancedNodes()
end

main()``````

#### input

`````` Balanced Node : 3
``````
``````// Scala program for
// Count balanced nodes present in a binary tree

// Binary Tree node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data,null,null);
}
}
class BinaryTree(var root: TreeNode , var count: Int)
{
def this()
{
this(null,0);
}
// This is Recursively find sum of left and right subtree
// and count balanced node.
def countBalancedNodes(node: TreeNode): Int = {
if (node == null)
{
return 0;
}
// Count sum of left subtree
var a: Int = countBalancedNodes(node.left);
// Count sum of right subtree
var b: Int = countBalancedNodes(node.right);
if (node.left != null && node.right != null && a == b)
{
// When left and right subtree not null
// And their sum are equal
this.count += 1;
}
// Sum of all left subtree right subtree and current node
return a + b + node.data;
}
def balancedNodes(): Unit = {
if (this.root == null)
{
print("\n Empty Tree \n");
}
this.count = 0;
countBalancedNodes(this.root);
print("\n Balanced Node : " + this.count + " \n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
4
/   \
-4     7
/ \     \
2   3     12
/   / \    / \
1  -1  -1  5   7
/            \
-2              2
-----------------
Constructing binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(-4);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.left = new TreeNode(-1);
tree.root.left.right.right = new TreeNode(-1);
tree.root.left.left = new TreeNode(2);
tree.root.left.left.left = new TreeNode(1);
tree.root.left.left.left.left = new TreeNode(-2);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(5);
tree.root.right.right.left.right = new TreeNode(2);
// Test
// Here [-4,3,12 ] is resultant node
// Because their left and right subtree sum is equal
tree.balancedNodes();
}
}``````

#### input

`` Balanced Node : 3``
``````// Swift 4 program for
// Count balanced nodes present in a binary tree

// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
var count: Int;
init()
{
self.root = nil;
self.count = 0;
}
// This is Recursively find sum of left and right subtree
// and count balanced node.
func countBalancedNodes(_ node: TreeNode? )->Int
{
if (node == nil)
{
return 0;
}
// Count sum of left subtree
let a: Int = self.countBalancedNodes(node!.left);
// Count sum of right subtree
let b: Int = self.countBalancedNodes(node!.right);
if (node!.left  != nil && node!.right  != nil && a == b)
{
// When left and right subtree not null
// And their sum are equal
self.count += 1;
}
// Sum of all left subtree right subtree and current node
return a + b + node!.data;
}
func balancedNodes()
{
if (self.root == nil)
{
print("\n Empty Tree ");
}
self.count = 0;
let _ = self.countBalancedNodes(self.root);
print("\n Balanced Node : ", self.count ," ");
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
4
/   \
-4     7
/ \     \
2   3     12
/   / \    / \
1  -1  -1  5   7
/            \
-2              2
-----------------
Constructing binary tree
*/
tree.root = TreeNode(4);
tree.root!.left = TreeNode(-4);
tree.root!.left!.right = TreeNode(3);
tree.root!.left!.right!.left = TreeNode(-1);
tree.root!.left!.right!.right = TreeNode(-1);
tree.root!.left!.left = TreeNode(2);
tree.root!.left!.left!.left = TreeNode(1);
tree.root!.left!.left!.left!.left = TreeNode(-2);
tree.root!.right = TreeNode(7);
tree.root!.right!.right = TreeNode(12);
tree.root!.right!.right!.right = TreeNode(7);
tree.root!.right!.right!.left = TreeNode(5);
tree.root!.right!.right!.left!.right = TreeNode(2);
// Test
// Here [-4,3,12 ] is resultant node
// Because their left and right subtree sum is equal
tree.balancedNodes();
}
main();``````

#### input

`` Balanced Node :  3``
``````// Kotlin program for
// Count balanced nodes present in a binary tree

// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
var count: Int;
constructor()
{
this.root = null;
this.count = 0;
}
// This is Recursively find sum of left and right subtree
// and count balanced node.
fun countBalancedNodes(node: TreeNode ? ): Int
{
if (node == null)
{
return 0;
}
// Count sum of left subtree
val a: Int = this.countBalancedNodes(node.left);
// Count sum of right subtree
val b: Int = this.countBalancedNodes(node.right);
if (node.left != null && node.right != null && a == b)
{
// When left and right subtree not null
// And their sum are equal
this.count += 1;
}
// Sum of all left subtree right subtree and current node
return a + b + node.data;
}
fun balancedNodes(): Unit
{
if (this.root == null)
{
print("\n Empty Tree \n");
}
this.count = 0;
this.countBalancedNodes(this.root);
print("\n Balanced Node : " + this.count + " \n");
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinaryTree = BinaryTree();
/*
4
/   \
-4     7
/ \     \
2   3     12
/   / \    / \
1  -1  -1  5   7
/            \
-2              2
-----------------
Constructing binary tree
*/
tree.root = TreeNode(4);
tree.root?.left = TreeNode(-4);
tree.root?.left?.right = TreeNode(3);
tree.root?.left?.right?.left = TreeNode(-1);
tree.root?.left?.right?.right = TreeNode(-1);
tree.root?.left?.left = TreeNode(2);
tree.root?.left?.left?.left = TreeNode(1);
tree.root?.left?.left?.left?.left = TreeNode(-2);
tree.root?.right = TreeNode(7);
tree.root?.right?.right = TreeNode(12);
tree.root?.right?.right?.right = TreeNode(7);
tree.root?.right?.right?.left = TreeNode(5);
tree.root?.right?.right?.left?.right = TreeNode(2);
// Test
// Here [-4,3,12 ] is resultant node
// Because their left and right subtree sum is equal
tree.balancedNodes();
}``````

#### input

`` Balanced Node : 3``

## Time Complexity

• Constructing the binary tree takes O(N) time, where N is the number of nodes in the tree.
• The `balancedNodes()` function traverses each node once, so it takes O(N) time.
• The total time complexity of the program is O(N).

## Space Complexity

• The space complexity is also O(N) because the program uses memory to store the binary tree structure and the recursion stack.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post