Check whether binary tree is form of max heap
Here given code implementation process.
/*
C Program
Check whether binary tree is form of max heap
*/
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Tree node
struct Node
{
int data;
struct Node*left,*right;
};
//Create a binary tree nodes and node fields (data,pointer)
//And returning the reference of newly nodes
struct Node* insert(int data)
{
//Create dynamic memory to new binary tree 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; //Initially node left-pointer is NULL
new_node->right=NULL;//Initially node right-pointer is NULL
}else
{
printf("Memory Overflow\n");
exit(0); //TerMaxate program execution
}
//return reference
return new_node;
}
//Check that given binary tree is form of max heap or not
int is_max_heap(struct Node*root)
{
if(root!=NULL)
{
if(root->left!=NULL && root->left->data > root->data ||
root->right!=NULL && root->right->data > root->data)
{
//When tree is not a max heap
return 0;
}
if(is_max_heap(root->left) == 1 && is_max_heap(root->right) == 1)
{
//When the tree is in the form of a max heap
return 1;
}
return 0;
}
return 1;
}
//Display tree element inorder form
void inorder(struct Node*node){
if(node){
inorder(node->left);
//Print node value
printf(" %d",node->data);
inorder(node->right);
}
}
int main(){
struct Node*root=NULL;
/* Make A Binary Tree
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \
6 2
/
1
*/
//Insertion of binary tree nodes
root =insert(17);
root->left =insert(15);
root->right =insert(16);
root->right->right =insert(10);
root->right->left =insert(8);
root->left->left =insert(9);
root->left->left->left =insert(6);
root->left->right =insert(7);
root->left->right->right =insert(2);
root->left->right->right->left=insert(1);
inorder(root);
if(is_max_heap(root)==1)
{
printf("\n Max Heap Binary Tree \n");
}
else
{
printf(" Not a Max Heap Binary Tree \n");
}
/* Make A Binary Tree
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \ \
6 2 20
/
1
*/
root->right->right->right =insert(20);
inorder(root);
if(is_max_heap(root)==1)
{
printf("\n Max Heap Binary Tree \n");
}
else
{
printf("\n Not a Max Heap Binary Tree \n");
}
return 0;
}
Output
6 9 15 7 1 2 17 8 16 10
Max Heap Binary Tree
6 9 15 7 1 2 17 8 16 10 20
Not a Max Heap Binary Tree/*
C++ Program
Check whether binary tree is form of max heap
*/
#include<iostream>
using namespace std;
//Structure of Binary Tree node
class Node {
public:
int data;
Node *left, *right;
//make a tree node
Node(int data) {
//assign field values
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class MyHeap {
public:
Node *root;
MyHeap() {
this->root = NULL;
}
//Check that given binary tree is form of max heap or not
bool is_max_heap(Node *root) {
if (root != NULL) {
if (root->left != NULL && root->left->data > root->data
|| root->right != NULL && root->right->data > root->data) {
return
//When tree is not a max heap
false;
}
if (this->is_max_heap(root->left) == true
&& this->is_max_heap(root->right) == true) {
return
//When the tree is in the form of a max heap
true;
}
return false;
}
return true;
}
//Display tree elements in order form
void inorder(Node *node) {
if (node != NULL) {
this->inorder(node->left);
//Print node value
cout << " " << node->data;
this->inorder(node->right);
}
}
};
int main() {
MyHeap obj = MyHeap();
/* Make A Binary Tree
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \
6 2
/
1
*/
//Insertion of binary tree nodes
obj.root = new Node(17);
obj.root->left = new Node(15);
obj.root->right = new Node(16);
obj.root->right->right = new Node(10);
obj.root->right->left = new Node(8);
obj.root->left->left = new Node(9);
obj.root->left->left->left = new Node(6);
obj.root->left->right = new Node(7);
obj.root->left->right->right = new Node(2);
obj.root->left->right->right->left = new Node(1);
obj.inorder(obj.root);
if (obj.is_max_heap(obj.root) == true) {
cout << "\n Max Heap Binary Tree \n";
} else {
cout << " Not a Max Heap Binary Tree \n";
}
/* Make A Binary Tree
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \ \
6 2 20
/
1
*/
obj.root->right->right->right = new Node(20);
obj.inorder(obj.root);
if (obj.is_max_heap(obj.root) == true) {
cout << "\n Max Heap Binary Tree \n";
} else {
cout << "\n Not a Max Heap Binary Tree \n";
}
return 0;
}
Output
6 9 15 7 1 2 17 8 16 10
Max Heap Binary Tree
6 9 15 7 1 2 17 8 16 10 20
Not a Max Heap Binary Tree/*
Java Program
Check whether binary tree is form of max heap
*/
//Structure of Binary Tree node
class Node
{
public int data;
public Node left, right;
//make a tree node
public Node(int data)
{
//assign field values
this.data=data;
left=null;
right=null;
}
}
public class MyHeap
{
public Node root;
public MyHeap()
{
root=null;
}
//Check that given binary tree is form of max heap or not
public boolean is_max_heap(Node root)
{
if(root!=null)
{
if(root.left!=null && root.left.data > root.data ||
root.right!=null && root.right.data > root.data)
{
//When tree is not a max heap
return false;
}
if(is_max_heap(root.left) == true && is_max_heap(root.right) == true)
{
//When the tree is in the form of a max heap
return true;
}
return false;
}
return true;
}
//Display tree elements in order form
public void inorder(Node node){
if(node!=null){
inorder(node.left);
//Print node value
System.out.print(" "+node.data);
inorder(node.right);
}
}
public static void main(String[] args) {
MyHeap obj = new MyHeap();
/* Make A Binary Tree
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \
6 2
/
1
*/
//Insertion of binary tree nodes
obj.root =new Node(17);
obj.root.left =new Node(15);
obj.root.right =new Node(16);
obj.root.right.right =new Node(10);
obj.root.right.left =new Node(8);
obj.root.left.left =new Node(9);
obj.root.left.left.left =new Node(6);
obj.root.left.right =new Node(7);
obj.root.left.right.right =new Node(2);
obj.root.left.right.right.left=new Node(1);
obj.inorder(obj.root);
if(obj.is_max_heap(obj.root)==true)
{
System.out.print("\n Max Heap Binary Tree \n");
}
else
{
System.out.print(" Not a Max Heap Binary Tree \n");
}
/* Make A Binary Tree
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \ \
6 2 20
/
1
*/
obj.root.right.right.right =new Node(20);
obj.inorder(obj.root);
if(obj.is_max_heap(obj.root)==true)
{
System.out.print("\n Max Heap Binary Tree \n");
}
else
{
System.out.print("\n Not a Max Heap Binary Tree \n");
}
}
}
Output
6 9 15 7 1 2 17 8 16 10
Max Heap Binary Tree
6 9 15 7 1 2 17 8 16 10 20
Not a Max Heap Binary Tree/*
C# Program
Check whether binary tree is form of max heap
*/
using System;
//Structure of Binary Tree node
public class Node {
public int data;
public Node left;
public Node right;
//make a tree node
public Node(int data) {
//assign field values
this.data = data;
left = null;
right = null;
}
}
public class MyHeap {
public Node root;
public MyHeap() {
root = null;
}
//Check that given binary tree is form of max heap or not
public Boolean is_max_heap(Node root) {
if (root != null) {
if (root.left != null && root.left.data > root.data || root.right != null && root.right.data > root.data) {
return false;
}
if (is_max_heap(root.left) == true && is_max_heap(root.right) == true) {
return true;
}
return false;
}
return true;
}
//Display tree elements in order form
public void inorder(Node node) {
if (node != null) {
inorder(node.left);
Console.Write(" " + node.data);
inorder(node.right);
}
}
public static void Main(String[] args) {
MyHeap obj = new MyHeap();
/* Make A Binary Tree
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \
6 2
/
1
*/
//Insertion of binary tree nodes
obj.root = new Node(17);
obj.root.left = new Node(15);
obj.root.right = new Node(16);
obj.root.right.right = new Node(10);
obj.root.right.left = new Node(8);
obj.root.left.left = new Node(9);
obj.root.left.left.left = new Node(6);
obj.root.left.right = new Node(7);
obj.root.left.right.right = new Node(2);
obj.root.left.right.right.left = new Node(1);
obj.inorder(obj.root);
if (obj.is_max_heap(obj.root) == true) {
Console.Write("\n Max Heap Binary Tree \n");
} else {
Console.Write(" Not a Max Heap Binary Tree \n");
}
/* Make A Binary Tree
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \ \
6 2 20
/
1
*/
obj.root.right.right.right = new Node(20);
obj.inorder(obj.root);
if (obj.is_max_heap(obj.root) == true) {
Console.Write("\n Max Heap Binary Tree \n");
} else {
Console.Write("\n Not a Max Heap Binary Tree \n");
}
}
}
Output
6 9 15 7 1 2 17 8 16 10
Max Heap Binary Tree
6 9 15 7 1 2 17 8 16 10 20
Not a Max Heap Binary Tree<?php
/*
Php Program
Check whether binary tree is form of max heap
*/
//Structure of Binary Tree node
class Node {
public $data;
public $left;
public $right;
//make a tree node
function __construct($data) {
//assign field values
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
class MyHeap {
public $root;
function __construct() {
$this->root = null;
}
//Check that given binary tree is form of max heap or not
public function is_max_heap($root) {
if ($root != null) {
if ($root->left != null && $root->left->data > $root->data || $root->right != null && $root->right->data > $root->data) {
return false;
}
if ($this->is_max_heap($root->left) == true && $this->is_max_heap($root->right) == true) {
return true;
}
return false;
}
return true;
}
//Display tree elements in order form
public function inorder($node) {
if ($node != null) {
$this->inorder($node->left);
//Print node value
echo(" ". $node->data);
$this->inorder($node->right);
}
}
}
function main() {
$obj = new MyHeap();
/* Make A Binary Tree
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \
6 2
/
1
*/
//Insertion of binary tree nodes
$obj->root = new Node(17);
$obj->root->left = new Node(15);
$obj->root->right = new Node(16);
$obj->root->right->right = new Node(10);
$obj->root->right->left = new Node(8);
$obj->root->left->left = new Node(9);
$obj->root->left->left->left = new Node(6);
$obj->root->left->right = new Node(7);
$obj->root->left->right->right = new Node(2);
$obj->root->left->right->right->left = new Node(1);
$obj->inorder($obj->root);
if (
$obj->is_max_heap($obj->root) == true) {
echo("\n Max Heap Binary Tree \n");
} else {
echo(" Not a Max Heap Binary Tree \n");
}
/* Make A Binary Tree
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \ \
6 2 20
/
1
*/
$obj->root->right->right->right = new Node(20);
$obj->inorder($obj->root);
if (
$obj->is_max_heap($obj->root) == true) {
echo("\n Max Heap Binary Tree \n");
} else {
echo("\n Not a Max Heap Binary Tree \n");
}
}
main();
Output
6 9 15 7 1 2 17 8 16 10
Max Heap Binary Tree
6 9 15 7 1 2 17 8 16 10 20
Not a Max Heap Binary Tree/*
Node Js Program
Check whether binary tree is form of max heap
*/
//Structure of Binary Tree node
class Node {
//make a tree node
constructor(data) {
//assign field values
this.data = data;
this.left = null;
this.right = null;
}
}
class MyHeap {
constructor() {
this.root = null;
}
//Check that given binary tree is form of max heap or not
is_max_heap(root) {
if (root != null) {
if (root.left != null && root.left.data > root.data || root.right != null && root.right.data > root.data) {
return false;
}
if (this.is_max_heap(root.left) == true && this.is_max_heap(root.right) == true) {
return true;
}
return false;
}
return true;
}
//Display tree elements in order form
inorder(node) {
if (node != null) {
this.inorder(node.left);
//Print node value
process.stdout.write(" " + node.data);
this.inorder(node.right);
}
}
}
function main(args) {
var obj = new MyHeap();
/* Make A Binary Tree
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \
6 2
/
1
*/
//Insertion of binary tree nodes
obj.root = new Node(17);
obj.root.left = new Node(15);
obj.root.right = new Node(16);
obj.root.right.right = new Node(10);
obj.root.right.left = new Node(8);
obj.root.left.left = new Node(9);
obj.root.left.left.left = new Node(6);
obj.root.left.right = new Node(7);
obj.root.left.right.right = new Node(2);
obj.root.left.right.right.left = new Node(1);
obj.inorder(obj.root);
if (obj.is_max_heap(obj.root) == true) {
process.stdout.write("\n Max Heap Binary Tree \n");
} else {
process.stdout.write(" Not a Max Heap Binary Tree \n");
}
/* Make A Binary Tree
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \ \
6 2 20
/
1
*/
obj.root.right.right.right = new Node(20);
obj.inorder(obj.root);
if (obj.is_max_heap(obj.root) == true) {
process.stdout.write("\n Max Heap Binary Tree \n");
} else {
process.stdout.write("\n Not a Max Heap Binary Tree \n");
}
}
main();
Output
6 9 15 7 1 2 17 8 16 10
Max Heap Binary Tree
6 9 15 7 1 2 17 8 16 10 20
Not a Max Heap Binary Tree# Python 3 Program
# Check whether binary tree is form of max heap
# Structure of Binary Tree node
class Node :
# make a tree node
def __init__(self, data) :
# assign field values
self.data = data
self.left = None
self.right = None
class MyHeap :
def __init__(self) :
self.root = None
# Check that given binary tree is form of max heap or not
def is_max_heap(self, root) :
if (root != None) :
if (root.left != None and root.left.data > root.data or root.right != None and root.right.data > root.data) :
return False
if (self.is_max_heap(root.left) == True and self.is_max_heap(root.right) == True) :
return True
return False
return True
# Display tree elements in order form
def inorder(self, node) :
if (node != None) :
self.inorder(node.left)
print(" ", node.data, end = "")
self.inorder(node.right)
def main() :
obj = MyHeap()
# Make A Binary Tree
# -----------------------
# 17
# / \
# 15 16
# / \ / \
# 9 7 8 10
# / \
# 6 2
# /
# 1
#
# Insertion of binary tree nodes
obj.root = Node(17)
obj.root.left = Node(15)
obj.root.right = Node(16)
obj.root.right.right = Node(10)
obj.root.right.left = Node(8)
obj.root.left.left = Node(9)
obj.root.left.left.left = Node(6)
obj.root.left.right = Node(7)
obj.root.left.right.right = Node(2)
obj.root.left.right.right.left = Node(1)
obj.inorder(obj.root)
if (obj.is_max_heap(obj.root) == True) :
print("\n Max Heap Binary Tree \n", end = "")
else :
print(" Not a Max Heap Binary Tree \n", end = "")
# Make A Binary Tree
# -----------------------
# 17
# / \
# 15 16
# / \ / \
# 9 7 8 10
# / \ \
# 6 2 20
# /
# 1
#
obj.root.right.right.right = Node(20)
obj.inorder(obj.root)
if (obj.is_max_heap(obj.root) == True) :
print("\n Max Heap Binary Tree \n", end = "")
else :
print("\n Not a Max Heap Binary Tree \n", end = "")
if __name__ == "__main__":
main()
Output
6 9 15 7 1 2 17 8 16 10
Max Heap Binary Tree
6 9 15 7 1 2 17 8 16 10 20
Not a Max Heap Binary Tree# Ruby Program
# Check whether binary tree is form of max heap
# Structure of Binary Tree node
class Node
# Define the accessor and reader of class Node
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
# make a tree node
def initialize(data)
# assign field values
self.data = data
@left = nil
@right = nil
end
end
class MyHeap
# Define the accessor and reader of class MyHeap
attr_reader :root
attr_accessor :root
def initialize()
@root = nil
end
# Check that given binary tree is form of max heap or not
def is_max_heap(root)
if (root != nil)
if (root.left != nil && root.left.data > root.data || root.right != nil && root.right.data > root.data)
return false
end
if (self.is_max_heap(root.left) == true && self.is_max_heap(root.right) == true)
return true
end
return false
end
return true
end
# Display tree elements in order form
def inorder(node)
if (node != nil)
self.inorder(node.left)
# Print node value
print(" ", node.data)
self.inorder(node.right)
end
end
end
def main()
obj = MyHeap.new()
# Make A Binary Tree
# -----------------------
# 17
# / \
# 15 16
# / \ / \
# 9 7 8 10
# / \
# 6 2
# /
# 1
#
# Insertion of binary tree nodes
obj.root = Node.new(17)
obj.root.left = Node.new(15)
obj.root.right = Node.new(16)
obj.root.right.right = Node.new(10)
obj.root.right.left = Node.new(8)
obj.root.left.left = Node.new(9)
obj.root.left.left.left = Node.new(6)
obj.root.left.right = Node.new(7)
obj.root.left.right.right = Node.new(2)
obj.root.left.right.right.left = Node.new(1)
obj.inorder(obj.root)
if (obj.is_max_heap(obj.root) == true)
print("\n Max Heap Binary Tree \n")
else
print(" Not a Max Heap Binary Tree \n")
end
# Make A Binary Tree
# -----------------------
# 17
# / \
# 15 16
# / \ / \
# 9 7 8 10
# / \ \
# 6 2 20
# /
# 1
#
obj.root.right.right.right = Node.new(20)
obj.inorder(obj.root)
if (obj.is_max_heap(obj.root) == true)
print("\n Max Heap Binary Tree \n")
else
print("\n Not a Max Heap Binary Tree \n")
end
end
main()
Output
6 9 15 7 1 2 17 8 16 10
Max Heap Binary Tree
6 9 15 7 1 2 17 8 16 10 20
Not a Max Heap Binary Tree
/*
Scala Program
Check whether binary tree is form of max heap
*/
//Structure of Binary Tree node
class Node(var data: Int,var left: Node,var right: Node) {
//make a tree node
def this(data: Int) {
//assign field values
this(data, null,null);
}
}
class MyHeap(var root: Node) {
def this() {
this(null);
}
//Check that given binary tree is form of max heap or not
def is_max_heap(root: Node): Boolean = {
if (root != null) {
if (root.left != null && root.left.data > root.data || root.right != null && root.right.data > root.data) {
return false;
}
if (this.is_max_heap(root.left) == true && this.is_max_heap(root.right) == true) {
return true;
}
return false;
}
return true;
}
//Display tree elements in order form
def inorder(node: Node): Unit = {
if (node != null) {
this.inorder(node.left);
//Print node value
print(" " + node.data);
this.inorder(node.right);
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyHeap = new MyHeap();
/* Make A Binary Tree
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \
6 2
/
1
*/
//Insertion of binary tree nodes
obj.root = new Node(17);
obj.root.left = new Node(15);
obj.root.right = new Node(16);
obj.root.right.right = new Node(10);
obj.root.right.left = new Node(8);
obj.root.left.left = new Node(9);
obj.root.left.left.left = new Node(6);
obj.root.left.right = new Node(7);
obj.root.left.right.right = new Node(2);
obj.root.left.right.right.left = new Node(1);
obj.inorder(obj.root);
if (obj.is_max_heap(obj.root) == true) {
print("\n Max Heap Binary Tree \n");
} else {
print(" Not a Max Heap Binary Tree \n");
}
/* Make A Binary Tree
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \ \
6 2 20
/
1
*/
obj.root.right.right.right = new Node(20);
obj.inorder(obj.root);
if (obj.is_max_heap(obj.root) == true) {
print("\n Max Heap Binary Tree \n");
} else {
print("\n Not a Max Heap Binary Tree \n");
}
}
}
Output
6 9 15 7 1 2 17 8 16 10
Max Heap Binary Tree
6 9 15 7 1 2 17 8 16 10 20
Not a Max Heap Binary Tree/*
Swift Program
Check whether binary tree is form of max heap
*/
//Structure of Binary Tree node
class Node {
var data: Int;
var left: Node?;
var right: Node?;
//make a tree node
init(_ data: Int) {
//assign field values
self.data = data;
self.left = nil;
self.right = nil;
}
}
class MyHeap {
var root: Node?;
init() {
self.root = nil;
}
//Check that given binary tree is form of max heap or not
func is_max_heap(_ root: Node?) -> Bool {
if (root != nil) {
if (root!.left != nil && root!.left!.data > root!.data || root!.right != nil && root!.right!.data > root!.data) {
return false;
}
if (self.is_max_heap(root!.left) == true && self.is_max_heap(root!.right) == true) {
return true;
}
return false;
}
return true;
}
//Display tree elements in order form
func inorder(_ node: Node?) {
if (node != nil) {
self.inorder(node!.left);
print(" ", node!.data, terminator: "");
self.inorder(node!.right);
}
}
}
func main() {
let obj: MyHeap = MyHeap();
/* Make A Binary Tree
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \
6 2
/
1
*/
//Insertion of binary tree nodes
obj.root = Node(17);
obj.root!.left = Node(15);
obj.root!.right = Node(16);
obj.root!.right!.right = Node(10);
obj.root!.right!.left = Node(8);
obj.root!.left!.left = Node(9);
obj.root!.left!.left!.left = Node(6);
obj.root!.left!.right = Node(7);
obj.root!.left!.right!.right = Node(2);
obj.root!.left!.right!.right!.left = Node(1);
obj.inorder(obj.root);
if (obj.is_max_heap(obj.root) == true) {
print("\n Max Heap Binary Tree \n", terminator: "");
} else {
print(" Not a Max Heap Binary Tree \n", terminator: "");
}
/* Add 20
-----------------------
17
/ \
15 16
/ \ / \
9 7 8 10
/ \ \
6 2 20
/
1
*/
obj.root!.right!.right!.right = Node(20);
obj.inorder(obj.root);
if (obj.is_max_heap(obj.root) == true) {
print("\n Max Heap Binary Tree \n", terminator: "");
} else {
print("\n Not a Max Heap Binary Tree \n", terminator: "");
}
}
main();
Output
6 9 15 7 1 2 17 8 16 10
Max Heap Binary Tree
6 9 15 7 1 2 17 8 16 10 20
Not a Max Heap Binary Tree
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