Count balanced nodes present in a binary tree
Here given code implementation process.
// 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_reader :data, :left, :right
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_reader :root, :count
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
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.
New Comment