Count half nodes in a Binary Tree
Here given code implementation process.
/*
C Program
Count half nodes in a Binary Tree
*/
#include <stdio.h>
#include <stdlib.h>
//Binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};
//This is creating a binary tree node and return this
struct Node *get_node(int data)
{
// Create dynamic node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
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;
}
//Display pre order elements
void preorder(struct Node *node)
{
if (node != NULL)
{
//Print node value
printf(" %d", node->data);
preorder(node->left);
preorder(node->right);
}
}
//Count half nodes
void count_half_nodes(struct Node *node, int *counter)
{
if (node == NULL || (node->left == NULL && node->right == NULL))
{
// When node is null node or node is a leaf node
return;
}
if (node->left == NULL || node->right == NULL)
{
//When node is single child node
*counter = *counter + 1;
}
// Recursively visit left and right subtree
count_half_nodes(node->left, counter);
count_half_nodes(node->right, counter);
}
//Handles the request to find half nodes in tree
void half_nodes(struct Node *root)
{
if (root == NULL)
{
printf("\n Empty Tree \n");
}
else
{
//Display tree elements
printf("\n Tree Nodes \n");
preorder(root);
int counter = 0;
count_half_nodes(root, & counter);
// Display calculated result
printf("\n Half Nodes : %d \n", counter);
}
}
int main()
{
struct Node *root = NULL;
/*
constructor binary tree
-----------------
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
\ \ \
9 4 12
/
15
-----------------
*/
root = get_node(8);
root->left = get_node(5);
root->left->right = get_node(3);
root->left->right->right = get_node(9);
root->left->right->right->left = get_node(15);
root->left->left = get_node(1);
root->right = get_node(10);
root->right->left = get_node(11);
root->right->left->right = get_node(4);
root->right->right = get_node(2);
root->right->right->right = get_node(12);
half_nodes(root);
return 0;
}Output
Tree Nodes
8 5 1 3 9 15 10 11 4 2 12
Half Nodes : 4/*
Java Program
Count half nodes in a Binary Tree
*/
// Binary Tree node
class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public Node root;
public int counter;
public BinaryTree()
{
//Set initial tree root to null
this.root = null;
//Set result counter
this.counter = 0;
}
//Display pre order elements
public void preorder(Node node)
{
if (node != null)
{
//Print node value
System.out.print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
//Count half nodes
public void count_half_nodes(Node node)
{
if (node == null || (node.left == null && node.right == null))
{
// When node is null node or node is a leaf node
return;
}
if (node.left == null || node.right == null)
{
//When node is single child node
this.counter = this.counter + 1;
}
// Recursively visit left and right subtree
count_half_nodes(node.left);
count_half_nodes(node.right);
}
//Handles the request to find half nodes in tree
public void half_nodes()
{
if (this.root == null)
{
System.out.print("\n Empty Tree \n");
}
else
{
//Display tree elements
System.out.print("\n Tree Nodes \n");
preorder(this.root);
this.counter = 0;
count_half_nodes(this.root);
// Display calculated result
System.out.print("\n Half Nodes : " + this.counter + " \n");
}
}
public static void main(String[] args)
{
//Create tree object
BinaryTree tree = new BinaryTree();
/*
constructor binary tree
-----------------
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
\ \ \
9 4 12
/
15
-----------------
*/
tree.root = new Node(8);
tree.root.left = new Node(5);
tree.root.left.right = new Node(3);
tree.root.left.right.right = new Node(9);
tree.root.left.right.right.left = new Node(15);
tree.root.left.left = new Node(1);
tree.root.right = new Node(10);
tree.root.right.left = new Node(11);
tree.root.right.left.right = new Node(4);
tree.root.right.right = new Node(2);
tree.root.right.right.right = new Node(12);
tree.half_nodes();
}
}Output
Tree Nodes
8 5 1 3 9 15 10 11 4 2 12
Half Nodes : 4// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Count half nodes in a Binary Tree
*/
// Binary Tree node
class Node
{
public: int data;
Node *left;
Node *right;
Node(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public: Node *root;
int counter;
BinaryTree()
{
// Set initial tree root to null
this->root = NULL;
// Set result counter
this->counter = 0;
}
// Display pre order elements
void preorder(Node *node)
{
if (node != NULL)
{
// Print node value
cout << " " << node->data;
this->preorder(node->left);
this->preorder(node->right);
}
}
// Count half nodes
void count_half_nodes(Node *node)
{
// When node is null node or node is a leaf node
if (node == NULL || (node->left == NULL && node->right == NULL))
{
return;
}
if (node->left == NULL || node->right == NULL)
{
// When node is single child node
this->counter = this->counter + 1;
}
// Recursively visit left and right subtree
this->count_half_nodes(node->left);
this->count_half_nodes(node->right);
}
// Handles the request to find half nodes in tree
void half_nodes()
{
if (this->root == NULL)
{
cout << "\n Empty Tree \n";
}
else
{
// Display tree elements
cout << "\n Tree Nodes \n";
this->preorder(this->root);
this->counter = 0;
this->count_half_nodes(this->root);
// Display calculated result
cout << "\n Half Nodes : " << this->counter << " \n";
}
}
};
int main()
{
// Create tree object
BinaryTree tree = BinaryTree();
/*
constructor binary tree
-----------------
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
\ \ \
9 4 12
/
15
-----------------
*/
tree.root = new Node(8);
tree.root->left = new Node(5);
tree.root->left->right = new Node(3);
tree.root->left->right->right = new Node(9);
tree.root->left->right->right->left = new Node(15);
tree.root->left->left = new Node(1);
tree.root->right = new Node(10);
tree.root->right->left = new Node(11);
tree.root->right->left->right = new Node(4);
tree.root->right->right = new Node(2);
tree.root->right->right->right = new Node(12);
tree.half_nodes();
return 0;
}Output
Tree Nodes
8 5 1 3 9 15 10 11 4 2 12
Half Nodes : 4// Include namespace system
using System;
/*
C# Program
Count half nodes in a Binary Tree
*/
// Binary Tree node
public class Node
{
public int data;
public Node left;
public Node right;
public Node(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public Node root;
public int counter;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
// Set result counter
this.counter = 0;
}
// Display pre order elements
public void preorder(Node node)
{
if (node != null)
{
// Print node value
Console.Write(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
// Count half nodes
public void count_half_nodes(Node node)
{
// When node is null node or node is a leaf node
if (node == null || (node.left == null && node.right == null))
{
return;
}
if (node.left == null || node.right == null)
{
// When node is single child node
this.counter = this.counter + 1;
}
// Recursively visit left and right subtree
count_half_nodes(node.left);
count_half_nodes(node.right);
}
// Handles the request to find half nodes in tree
public void half_nodes()
{
if (this.root == null)
{
Console.Write("\n Empty Tree \n");
}
else
{
// Display tree elements
Console.Write("\n Tree Nodes \n");
preorder(this.root);
this.counter = 0;
count_half_nodes(this.root);
// Display calculated result
Console.Write("\n Half Nodes : " + this.counter + " \n");
}
}
public static void Main(String[] args)
{
// Create tree object
BinaryTree tree = new BinaryTree();
/*
constructor binary tree
-----------------
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
\ \ \
9 4 12
/
15
-----------------
*/
tree.root = new Node(8);
tree.root.left = new Node(5);
tree.root.left.right = new Node(3);
tree.root.left.right.right = new Node(9);
tree.root.left.right.right.left = new Node(15);
tree.root.left.left = new Node(1);
tree.root.right = new Node(10);
tree.root.right.left = new Node(11);
tree.root.right.left.right = new Node(4);
tree.root.right.right = new Node(2);
tree.root.right.right.right = new Node(12);
tree.half_nodes();
}
}Output
Tree Nodes
8 5 1 3 9 15 10 11 4 2 12
Half Nodes : 4<?php
/*
Php Program
Count half nodes in a Binary Tree
*/
// Binary Tree node
class Node
{
public $data;
public $left;
public $right;
function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
class BinaryTree
{
public $root;
public $counter;
function __construct()
{
// Set initial tree root to null
$this->root = null;
// Set result counter
$this->counter = 0;
}
// Display pre order elements
public function preorder($node)
{
if ($node != null)
{
// Print node value
echo " ". $node->data;
$this->preorder($node->left);
$this->preorder($node->right);
}
}
// Count half nodes
public function count_half_nodes($node)
{
// When node is null node or node is a leaf node
if ($node == null || ($node->left == null && $node->right == null))
{
return;
}
if ($node->left == null || $node->right == null)
{
// When node is single child node
$this->counter = $this->counter + 1;
}
// Recursively visit left and right subtree
$this->count_half_nodes($node->left);
$this->count_half_nodes($node->right);
}
// Handles the request to find half nodes in tree
public function half_nodes()
{
if ($this->root == null)
{
echo "\n Empty Tree \n";
}
else
{
// Display tree elements
echo "\n Tree Nodes \n";
$this->preorder($this->root);
$this->counter = 0;
$this->count_half_nodes($this->root);
// Display calculated result
echo "\n Half Nodes : ". $this->counter ." \n";
}
}
}
function main()
{
// Create tree object
$tree = new BinaryTree();
/*
constructor binary tree
-----------------
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
\ \ \
9 4 12
/
15
-----------------
*/
$tree->root = new Node(8);
$tree->root->left = new Node(5);
$tree->root->left->right = new Node(3);
$tree->root->left->right->right = new Node(9);
$tree->root->left->right->right->left = new Node(15);
$tree->root->left->left = new Node(1);
$tree->root->right = new Node(10);
$tree->root->right->left = new Node(11);
$tree->root->right->left->right = new Node(4);
$tree->root->right->right = new Node(2);
$tree->root->right->right->right = new Node(12);
$tree->half_nodes();
}
main();Output
Tree Nodes
8 5 1 3 9 15 10 11 4 2 12
Half Nodes : 4/*
Node Js Program
Count half nodes in a Binary Tree
*/
// Binary Tree node
class Node
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
// Set initial tree root to null
this.root = null;
// Set result counter
this.counter = 0;
}
// Display pre order elements
preorder(node)
{
if (node != null)
{
// Print node value
process.stdout.write(" " + node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
// Count half nodes
count_half_nodes(node)
{
// When node is null node or node is a leaf node
if (node == null || (node.left == null && node.right == null))
{
return;
}
if (node.left == null || node.right == null)
{
// When node is single child node
this.counter = this.counter + 1;
}
// Recursively visit left and right subtree
this.count_half_nodes(node.left);
this.count_half_nodes(node.right);
}
// Handles the request to find half nodes in tree
half_nodes()
{
if (this.root == null)
{
process.stdout.write("\n Empty Tree \n");
}
else
{
// Display tree elements
process.stdout.write("\n Tree Nodes \n");
this.preorder(this.root);
this.counter = 0;
this.count_half_nodes(this.root);
// Display calculated result
process.stdout.write("\n Half Nodes : " + this.counter + " \n");
}
}
}
function main()
{
// Create tree object
var tree = new BinaryTree();
/*
constructor binary tree
-----------------
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
\ \ \
9 4 12
/
15
-----------------
*/
tree.root = new Node(8);
tree.root.left = new Node(5);
tree.root.left.right = new Node(3);
tree.root.left.right.right = new Node(9);
tree.root.left.right.right.left = new Node(15);
tree.root.left.left = new Node(1);
tree.root.right = new Node(10);
tree.root.right.left = new Node(11);
tree.root.right.left.right = new Node(4);
tree.root.right.right = new Node(2);
tree.root.right.right.right = new Node(12);
tree.half_nodes();
}
main();Output
Tree Nodes
8 5 1 3 9 15 10 11 4 2 12
Half Nodes : 4# Python 3 Program
# Count half nodes in a Binary Tree
# Binary Tree node
class Node :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
# Set initial tree root to null
self.root = None
# Set result counter
self.counter = 0
# Display pre order elements
def preorder(self, node) :
if (node != None) :
# Print node value
print(" ", node.data, end = "")
self.preorder(node.left)
self.preorder(node.right)
# Count half nodes
def count_half_nodes(self, node) :
if (node == None or(node.left == None and node.right == None)) :
# When node is null node or node is a leaf node
return
if (node.left == None or node.right == None) :
# When node is single child node
self.counter = self.counter + 1
# Recursively visit left and right subtree
self.count_half_nodes(node.left)
self.count_half_nodes(node.right)
# Handles the request to find half nodes in tree
def half_nodes(self) :
if (self.root == None) :
print("\n Empty Tree \n", end = "")
else :
# Display tree elements
print("\n Tree Nodes \n", end = "")
self.preorder(self.root)
self.counter = 0
self.count_half_nodes(self.root)
# Display calculated result
print("\n Half Nodes : ", self.counter ," \n", end = "")
def main() :
# Create tree object
tree = BinaryTree()
#
# constructor binary tree
# -----------------
# 8
# / \
# / \
# / \
# 5 10
# / \ / \
# 1 3 11 2
# \ \ \
# 9 4 12
# /
# 15
# -----------------
#
tree.root = Node(8)
tree.root.left = Node(5)
tree.root.left.right = Node(3)
tree.root.left.right.right = Node(9)
tree.root.left.right.right.left = Node(15)
tree.root.left.left = Node(1)
tree.root.right = Node(10)
tree.root.right.left = Node(11)
tree.root.right.left.right = Node(4)
tree.root.right.right = Node(2)
tree.root.right.right.right = Node(12)
tree.half_nodes()
if __name__ == "__main__": main()Output
Tree Nodes
8 5 1 3 9 15 10 11 4 2 12
Half Nodes : 4# Ruby Program
# Count half nodes in a Binary Tree
# Binary Tree node
class Node
# Define the accessor and reader of class Node
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, :counter
attr_accessor :root, :counter
def initialize()
# Set initial tree root to null
self.root = nil
# Set result counter
self.counter = 0
end
# Display pre order elements
def preorder(node)
if (node != nil)
# Print node value
print(" ", node.data)
self.preorder(node.left)
self.preorder(node.right)
end
end
# Count half nodes
def count_half_nodes(node)
if (node == nil || (node.left == nil && node.right == nil))
# When node is null node or node is a leaf node
return
end
if (node.left == nil || node.right == nil)
# When node is single child node
self.counter = self.counter + 1
end
# Recursively visit left and right subtree
self.count_half_nodes(node.left)
self.count_half_nodes(node.right)
end
# Handles the request to find half nodes in tree
def half_nodes()
if (self.root == nil)
print("\n Empty Tree \n")
else
# Display tree elements
print("\n Tree Nodes \n")
self.preorder(self.root)
self.counter = 0
self.count_half_nodes(self.root)
# Display calculated result
print("\n Half Nodes : ", self.counter ," \n")
end
end
end
def main()
# Create tree object
tree = BinaryTree.new()
#
# constructor binary tree
# -----------------
# 8
# / \
# / \
# / \
# 5 10
# / \ / \
# 1 3 11 2
# \ \ \
# 9 4 12
# /
# 15
# -----------------
#
tree.root = Node.new(8)
tree.root.left = Node.new(5)
tree.root.left.right = Node.new(3)
tree.root.left.right.right = Node.new(9)
tree.root.left.right.right.left = Node.new(15)
tree.root.left.left = Node.new(1)
tree.root.right = Node.new(10)
tree.root.right.left = Node.new(11)
tree.root.right.left.right = Node.new(4)
tree.root.right.right = Node.new(2)
tree.root.right.right.right = Node.new(12)
tree.half_nodes()
end
main()Output
Tree Nodes
8 5 1 3 9 15 10 11 4 2 12
Half Nodes : 4
/*
Scala Program
Count half nodes in a Binary Tree
*/
// Binary Tree node
class Node(var data: Int , var left: Node , var right: Node)
{
def this(data: Int)
{
this(data, null, null);
}
}
class BinaryTree(var root: Node , var counter: Int)
{
def this()
{
this(null, 0);
}
// Display pre order elements
def preorder(node: Node): Unit = {
if (node != null)
{
// Print node value
print(" " + node.data);
preorder(node.left);
preorder(node.right);
}
}
// Count half nodes
def count_half_nodes(node: Node): Unit = {
// When node is null node or node is a leaf node
if (node == null || (node.left == null && node.right == null))
{
return;
}
if (node.left == null || node.right == null)
{
// When node is single child node
this.counter = this.counter + 1;
}
// Recursively visit left and right subtree
count_half_nodes(node.left);
count_half_nodes(node.right);
}
// Handles the request to find half nodes in tree
def half_nodes(): Unit = {
if (this.root == null)
{
print("\n Empty Tree \n");
}
else
{
// Display tree elements
print("\n Tree Nodes \n");
preorder(this.root);
this.counter = 0;
count_half_nodes(this.root);
// Display calculated result
print("\n Half Nodes : " + this.counter + " \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create tree object
var tree: BinaryTree = new BinaryTree();
/*
constructor binary tree
-----------------
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
\ \ \
9 4 12
/
15
-----------------
*/
tree.root = new Node(8);
tree.root.left = new Node(5);
tree.root.left.right = new Node(3);
tree.root.left.right.right = new Node(9);
tree.root.left.right.right.left = new Node(15);
tree.root.left.left = new Node(1);
tree.root.right = new Node(10);
tree.root.right.left = new Node(11);
tree.root.right.left.right = new Node(4);
tree.root.right.right = new Node(2);
tree.root.right.right.right = new Node(12);
tree.half_nodes();
}
}Output
Tree Nodes
8 5 1 3 9 15 10 11 4 2 12
Half Nodes : 4/*
Swift 4 Program
Count half nodes in a Binary Tree
*/
// Binary Tree node
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: Node? ;
var counter: Int;
init()
{
// Set initial tree root to null
self.root = nil;
// Set result counter
self.counter = 0;
}
// Display pre order elements
func preorder(_ node: Node? )
{
if (node != nil)
{
// Print node value
print(" ", node!.data, terminator: "");
self.preorder(node!.left);
self.preorder(node!.right);
}
}
// Count half nodes
func count_half_nodes(_ node: Node? )
{
// When node is null node or node is a leaf node
if (node == nil || (node!.left == nil && node!.right == nil))
{
return;
}
if (node!.left == nil || node!.right == nil)
{
// When node is single child node
self.counter = self.counter + 1;
}
// Recursively visit left and right subtree
self.count_half_nodes(node!.left);
self.count_half_nodes(node!.right);
}
// Handles the request to find half nodes in tree
func half_nodes()
{
if (self.root == nil)
{
print("\n Empty Tree \n", terminator: "");
}
else
{
// Display tree elements
print("\n Tree Nodes \n", terminator: "");
self.preorder(self.root);
self.counter = 0;
self.count_half_nodes(self.root);
// Display calculated result
print("\n Half Nodes : ", self.counter ," \n", terminator: "");
}
}
}
func main()
{
// Create tree object
let tree: BinaryTree = BinaryTree();
/*
constructor binary tree
-----------------
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
\ \ \
9 4 12
/
15
-----------------
*/
tree.root = Node(8);
tree.root!.left = Node(5);
tree.root!.left!.right = Node(3);
tree.root!.left!.right!.right = Node(9);
tree.root!.left!.right!.right!.left = Node(15);
tree.root!.left!.left = Node(1);
tree.root!.right = Node(10);
tree.root!.right!.left = Node(11);
tree.root!.right!.left!.right = Node(4);
tree.root!.right!.right = Node(2);
tree.root!.right!.right!.right = Node(12);
tree.half_nodes();
}
main();Output
Tree Nodes
8 5 1 3 9 15 10 11 4 2 12
Half Nodes : 4
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