Check if a given BST is height balanced
Here given code implementation process.
//C Program
//Check if a given BST is height balanced
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Search Tree node
struct Node
{
int data;
struct Node *left,*right;
};
//Adding a new node in binary search tree
void add( struct Node **root, int data)
{
//Create a dynamic node of binary search tree
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
if(*root == NULL)
{
//When adds a first node in binary tree
*root = new_node;
}
else
{
struct Node *find = *root;
//iterate binary tree and add new node to proper position
while(find != NULL)
{
if(find -> data > data)
{
if(find->left==NULL)
{
find->left = new_node;
break;
}
else
{ //visit left sub-tree
find = find->left;
}
}
else
{
if(find->right == NULL)
{
find->right = new_node;
break;
}
else
{
//visit right sub-tree
find = find->right;
}
}
}
}
}else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
}
int height(struct Node*root ,int *status)
{
if(root != NULL && *status==1)
{
int a = height(root->left,status);
int b = height(root->right,status);
if(a>b)
{
if(a-1!=b)
{
*status=0;
}
return a+1;
}
else
{
if(b!=a && b-1!=a)
{
*status=0;
}
return b+1;
}
}
return 0;
}
void inorder(struct Node*root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%3d ",root->data );
inorder(root->right);
}
}
void check_height(struct Node*root)
{
if(root != NULL)
{
int status=1;
inorder(root);
printf("\n");
height(root,&status);
if(status==1)
{
printf(" Height Balanced BST\n");
}
else
{
printf(" Not Height Balanced BST\n");
}
printf("\n");
}
}
int main(){
struct Node*root = NULL;
//Add nodes in binary search tree
/*
5
/ \
3 9
/ \
1 4
/ \
-3 2
*/
add(&root,5);
add(&root,3);
add(&root,9);
add(&root,1);
add(&root,4);
add(&root,-3);
add(&root,2);
check_height(root);
/*
5
/ \
3 9
/ \ /
1 4 8
/ \
-3 2
*/
add(&root,8);
check_height(root);
return 0;
}
Output
-3 1 2 3 4 5 9
Not Height Balanced BST
-3 1 2 3 4 5 8 9
Height Balanced BST
/*
C++ Program
Check if a given BST is height balanced
*/
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left;
Node *right;
Node(int value) {
this->data = value;
this->left = NULL;
this->right = NULL;
}
};
class BinarySearchTree {
public:
Node *root;
bool status;
BinarySearchTree() {
this->root = NULL;
this->status = false;
}
void add(int value) {
Node *new_node = new Node(value);
if (new_node != NULL) {
if (this->root == NULL) {
this->root = new_node;
} else {
Node *find = this->root;
while (find != NULL) {
if (find->data >= value) {
if (find->left == NULL) {
find->left = new_node;
break;
} else {
find = find->left;
}
} else {
if (find->right == NULL) {
find->right = new_node;
break;
} else {
find = find->right;
}
}
}
}
} else {
cout << "\nMemory Overflow\n";
}
}
int height(Node *head) {
if (head != NULL && this->status == true) {
int a = this->height(head->left);
int b = this->height(head->right);
if (a > b) {
if (a - 1 != b) {
this->status = false;
}
return a + 1;
} else {
if (b != a && b - 1 != a) {
this->status = false;
}
return b + 1;
}
}
return 0;
}
void inorder(Node *head) {
if (head != NULL) {
this->inorder(head->left);
cout << " " << head->data;
this->inorder(head->right);
}
}
void check_height() {
if (this->root != NULL) {
this->status = true;
this->inorder(this->root);
cout << ("\n");
this->height(this->root);
if (this->status == true) {
cout << " Height Balanced BST\n";
} else {
cout << " Not Height Balanced BST\n";
}
cout << ("\n");
}
}
};
int main() {
BinarySearchTree obj ;
/*
5
/ \
3 9
/ \
1 4
/ \
-3 2
*/
obj.add(5);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(4);
obj.add(-3);
obj.add(2);
obj.check_height();
obj.add(8);
/*
5
/ \
3 9
/ \ /
1 4 8
/ \
-3 2
*/
obj.check_height();
return 0;
}
Output
-3 1 2 3 4 5 9
Not Height Balanced BST
-3 1 2 3 4 5 8 9
Height Balanced BST
//Java program
//Check if a given BST is height balanced
class Node {
public int data;
public Node left;
public Node right;
public Node(int value) {
data = value;
left = null;
right = null;
}
}
public class BinarySearchTree {
public Node root;
public boolean status;
BinarySearchTree() {
root = null;
status = false;
}
//insert a node in BST
public void add(int value) {
//Create a dynamic node of binary search tree
Node new_node = new Node(value);
if (new_node != null) {
if (root == null) {
//When adds a first node in binary tree
root = new_node;
} else {
Node find = root;
//add new node to proper position
while (find != null) {
if (find.data >= value) {
if (find.left == null) {
find.left = new_node;
break;
} else {
//visit left sub-tree
find = find.left;
}
} else {
if (find.right == null) {
find.right = new_node;
break;
} else {
//visit right sub-tree
find = find.right;
}
}
}
}
} else {
System.out.print("\nMemory Overflow\n");
}
}
public int height(Node head) {
if (head != null && this.status == true) {
int a = height(head.left);
int b = height(head.right);
if (a > b) {
if (a - 1 != b) {
this.status = false;
}
return a + 1;
} else {
if (b != a && b - 1 != a) {
this.status = false;
}
return b + 1;
}
}
return 0;
}
public void inorder(Node head) {
if (head != null) {
inorder(head.left);
System.out.print(" " + head.data);
inorder(head.right);
}
}
public void check_height() {
if (this.root != null) {
this.status = true;
inorder(this.root);
System.out.print("\n");
height(root);
if (status == true) {
System.out.print(" Height Balanced BST\n");
} else {
System.out.print(" Not Height Balanced BST\n");
}
System.out.print("\n");
}
}
public static void main(String[] args) {
BinarySearchTree obj = new BinarySearchTree();
//Add nodes in binary search tree
/*
5
/ \
3 9
/ \
1 4
/ \
-3 2
*/
obj.add(5);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(4);
obj.add(-3);
obj.add(2);
obj.check_height();
/*
5
/ \
3 9
/ \ /
1 4 8
/ \
-3 2
*/
obj.add(8);
obj.check_height();
}
}
Output
-3 1 2 3 4 5 9
Not Height Balanced BST
-3 1 2 3 4 5 8 9
Height Balanced BST
//C# program
//Check if a given BST is height balanced
using System;
public class Node {
public int data;
public Node left;
public Node right;
public Node(int value) {
data = value;
left = null;
right = null;
}
}
public class BinarySearchTree {
public Node root;
public Boolean status;
BinarySearchTree() {
root = null;
status = false;
}
//insert a node in BST
public void add(int value) {
//Create a dynamic node of binary search tree
Node new_node = new Node(value);
if (new_node != null) {
if (root == null) {
//When adds a first node in binary tree
root = new_node;
} else {
Node find = root;
//add new node to proper position
while (find != null) {
if (find.data >= value) {
if (find.left == null) {
find.left = new_node;
break;
} else {
//visit left sub-tree
find = find.left;
}
} else {
if (find.right == null) {
find.right = new_node;
break;
} else {
//visit right sub-tree
find = find.right;
}
}
}
}
} else {
Console.Write("\nMemory Overflow\n");
}
}
public int height(Node head) {
if (head != null && this.status == true) {
int a = height(head.left);
int b = height(head.right);
if (a > b) {
if (a - 1 != b) {
this.status = false;
}
return a + 1;
} else {
if (b != a && b - 1 != a) {
this.status = false;
}
return b + 1;
}
}
return 0;
}
public void inorder(Node head) {
if (head != null) {
inorder(head.left);
Console.Write(" " + head.data);
inorder(head.right);
}
}
public void check_height() {
if (this.root != null) {
this.status = true;
inorder(this.root);
Console.Write("\n");
height(root);
if (status == true) {
Console.Write(" Height Balanced BST\n");
} else {
Console.Write(" Not Height Balanced BST\n");
}
Console.Write("\n");
}
}
public static void Main(String[] args) {
BinarySearchTree obj = new BinarySearchTree();
//Add nodes in binary search tree
/*
5
/ \
3 9
/ \
1 4
/ \
-3 2
*/
obj.add(5);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(4);
obj.add(-3);
obj.add(2);
obj.check_height();
/*
5
/ \
3 9
/ \ /
1 4 8
/ \
-3 2
*/
obj.add(8);
obj.check_height();
}
}
Output
-3 1 2 3 4 5 9
Not Height Balanced BST
-3 1 2 3 4 5 8 9
Height Balanced BST
# Python 3 Program
# Check if a given BST is height balanced
class Node :
def __init__(self, value) :
self.data = value
self.left = None
self.right = None
class BinarySearchTree :
def __init__(self) :
self.root = None
self.status = False
def add(self, value) :
new_node = Node(value)
if (new_node != None) :
if (self.root == None) :
self.root = new_node
else :
find = self.root
while (find != None) :
if (find.data >= value) :
if (find.left == None) :
find.left = new_node
break
else :
find = find.left
else :
if (find.right == None) :
find.right = new_node
break
else :
find = find.right
else :
print("\nMemory Overflow\n")
def height(self, head) :
if (head != None and self.status == True) :
a = self.height(head.left)
b = self.height(head.right)
if (a > b) :
if (a - 1 != b) :
self.status = False
return a + 1
else :
if (b != a and b - 1 != a) :
self.status = False
return b + 1
return 0
def inorder(self, head) :
if (head != None) :
self.inorder(head.left)
print( head.data,end=" ")
self.inorder(head.right)
def check_height(self) :
if (self.root != None) :
self.status = True
self.inorder(self.root)
print()
self.height(self.root)
if (self.status == True) :
print(" Height Balanced BST\n")
else :
print(" Not Height Balanced BST\n")
def main() :
obj = BinarySearchTree()
obj.add(5)
obj.add(3)
obj.add(9)
obj.add(1)
obj.add(4)
obj.add(-3)
obj.add(2)
obj.check_height()
obj.add(8)
obj.check_height()
if __name__ == "__main__":
main()
Output
-3 1 2 3 4 5 9
Not Height Balanced BST
-3 1 2 3 4 5 8 9
Height Balanced BST
# Ruby Program
# Check if a given BST is height balanced
class Node
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(value)
@data = value
@left = nil
@right = nil
end
end
class BinarySearchTree
attr_reader :root, :status
attr_accessor :root, :status
def initialize()
@root = nil
@status = false
end
def add(value)
new_node = Node.new(value)
if (new_node != nil)
if (@root == nil)
@root = new_node
else
find = @root
while (find != nil)
if (find.data >= value)
if (find.left == nil)
find.left = new_node
break
else
find = find.left
end
else
if (find.right == nil)
find.right = new_node
break
else
find = find.right
end
end
end
end
else
print("\nMemory Overflow\n")
end
end
def height(head)
if (head != nil and self.status == true)
a = self.height(head.left)
b = self.height(head.right)
if (a > b)
if (a - 1 != b)
self.status = false
end
return a + 1
else
if (b != a and b - 1 != a)
self.status = false
end
return b + 1
end
end
return 0
end
def inorder(head)
if (head != nil)
self.inorder(head.left)
print(" ", head.data)
self.inorder(head.right)
end
end
def check_height()
if (self.root != nil)
self.status = true
self.inorder(self.root)
print("\n")
self.height(@root)
if (@status == true)
print(" Height Balanced BST\n")
else
print(" Not Height Balanced BST\n")
end
print("\n")
end
end
end
def main()
obj = BinarySearchTree.new()
obj.add(5)
obj.add(3)
obj.add(9)
obj.add(1)
obj.add(4)
obj.add(-3)
obj.add(2)
obj.check_height()
obj.add(8)
obj.check_height()
end
main()
Output
-3 1 2 3 4 5 9
Not Height Balanced BST
-3 1 2 3 4 5 8 9
Height Balanced BST
<?php
/*
Php Program
Check if a given BST is height balanced
*/
class Node {
public $data;
public $left;
public $right;
function __construct($value) {
$this->data = $value;
$this->left = null;
$this->right = null;
}
}
class BinarySearchTree {
public $root;
public $status;
function __construct() {
$this->root = null;
$this->status = false;
}
public function add($value) {
$new_node = new Node($value);
if ($new_node != null) {
if ($this->root == null) {
$this->root = $new_node;
} else {
$find = $this->root;
while ($find != null) {
if ($find->data >= $value) {
if ($find->left == null) {
$find->left = $new_node;
break;;
} else {
$find = $find->left;
}
} else {
if ($find->right == null) {
$find->right = $new_node;
break;;
} else {
$find = $find->right;
}
}
}
}
} else {
echo("\nMemory Overflow\n");
}
}
public function height($head) {
if ($head != null && $this->status == true) {
$a = $this->height($head->left);
$b = $this->height($head->right);
if ($a > $b) {
if ($a - 1 != $b) {
$this->status = false;
}
return $a + 1;
} else {
if ($b != $a && $b - 1 != $a) {
$this->status = false;
}
return $b + 1;
}
}
return 0;
}
public function inorder($head) {
if ($head != null) {
$this->inorder($head->left);
echo(" ". $head->data);
$this->inorder($head->right);
}
}
public function check_height() {
if ($this->root != null) {
$this->status = true;
$this->inorder($this->root);
echo("\n");
$this->height($this->root);
if ($this->status == true) {
echo(" Height Balanced BST\n");
} else {
echo(" Not Height Balanced BST\n");
}
echo("\n");
}
}
}
function main() {
$obj = new BinarySearchTree();
/*
5
/ \
3 9
/ \
1 4
/ \
-3 2
*/
$obj->add(5);
$obj->add(3);
$obj->add(9);
$obj->add(1);
$obj->add(4);
$obj->add(-3);
$obj->add(2);
$obj->check_height();
$obj->add(8);
/*
5
/ \
3 9
/ \ /
1 4 8
/ \
-3 2
*/
$obj->check_height();
}
main();
Output
-3 1 2 3 4 5 9
Not Height Balanced BST
-3 1 2 3 4 5 8 9
Height Balanced BST
/*
Node Js Program
Check if a given BST is height balanced
*/
class Node {
constructor(value) {
this.data = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
this.status = false;
}
add(value) {
var new_node = new Node(value);
if (new_node != null) {
if (this.root == null) {
this.root = new_node;
} else {
var find = this.root;
while (find != null) {
if (find.data >= value) {
if (find.left == null) {
find.left = new_node;
break;;
} else {
find = find.left;
}
} else {
if (find.right == null) {
find.right = new_node;
break;;
} else {
find = find.right;
}
}
}
}
} else {
process.stdout.write("\nMemory Overflow\n");
}
}
height(head) {
if (head != null && this.status == true) {
var a = this.height(head.left);
var b = this.height(head.right);
if (a > b) {
if (a - 1 != b) {
this.status = false;
}
return a + 1;
} else {
if (b != a && b - 1 != a) {
this.status = false;
}
return b + 1;
}
}
return 0;
}
inorder(head) {
if (head != null) {
this.inorder(head.left);
process.stdout.write(" " + head.data);
this.inorder(head.right);
}
}
check_height() {
if (this.root != null) {
this.status = true;
this.inorder(this.root);
process.stdout.write("\n");
this.height(this.root);
if (this.status == true) {
process.stdout.write(" Height Balanced BST\n");
} else {
process.stdout.write(" Not Height Balanced BST\n");
}
process.stdout.write("\n");
}
}
}
function main() {
var obj = new BinarySearchTree();
/*
5
/ \
3 9
/ \
1 4
/ \
-3 2
*/
obj.add(5);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(4);
obj.add(-3);
obj.add(2);
obj.check_height();
obj.add(8);
/*
5
/ \
3 9
/ \ /
1 4 8
/ \
-3 2
*/
obj.check_height();
}
main();
Output
-3 1 2 3 4 5 9
Not Height Balanced BST
-3 1 2 3 4 5 8 9
Height Balanced BST
/*
Swift 4 Program
Check if a given BST is height balanced
*/
class Node {
var data: Int;
var left: Node? ;
var right: Node? ;
init(_ value: Int) {
self.data = value;
self.left = nil;
self.right = nil;
}
}
class BinarySearchTree {
var root: Node? ;
var status: Bool;
init() {
self.root = nil;
self.status = false;
}
func add(_ value: Int) {
let new_node: Node? = Node(value);
if (new_node != nil) {
if (self.root == nil) {
self.root = new_node;
} else {
var find: Node? = self.root;
while (find != nil) {
if (find!.data >= value) {
if (find!.left == nil) {
find!.left = new_node;
break;
} else {
find = find!.left;
}
} else {
if (find!.right == nil) {
find!.right = new_node;
break;
} else {
find = find!.right;
}
}
}
}
} else {
print("\nMemory Overflow\n");
}
}
func height(_ head: Node? ) -> Int {
if (head != nil && self.status == true) {
let a: Int = self.height(head!.left);
let b: Int = self.height(head!.right);
if (a > b) {
if (a - 1 != b) {
self.status = false;
}
return a + 1;
} else {
if (b != a && b - 1 != a) {
self.status = false;
}
return b + 1;
}
}
return 0;
}
func inorder(_ head: Node? ) {
if (head != nil) {
self.inorder(head!.left);
print(head!.data, terminator:" ");
self.inorder(head!.right);
}
}
func check_height() {
if (self.root != nil) {
self.status = true;
self.inorder(self.root);
print();
var _ = self.height(self.root);
if (self.status == true) {
print(" Height Balanced BST\n");
} else {
print(" Not Height Balanced BST\n");
}
}
}
}
func main() {
let obj: BinarySearchTree = BinarySearchTree();
/*
5
/ \
3 9
/ \
1 4
/ \
-3 2
*/
obj.add(5);
obj.add(3);
obj.add(9);
obj.add(1);
obj.add(4);
obj.add(-3);
obj.add(2);
obj.check_height();
obj.add(8);
/*
5
/ \
3 9
/ \ /
1 4 8
/ \
-3 2
*/
obj.check_height();
}
main();
Output
-3 1 2 3 4 5 9
Not Height Balanced BST
-3 1 2 3 4 5 8 9
Height Balanced BST
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