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_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

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.

New Comment