Height of the Binary Search Tree
#include<stdio.h>
#include<stdlib.h>
struct BST
{
int
data;
struct
BST *lchild;
struct
BST *rchild;
};
typedef struct BST * NODE;
NODE get_node()
{
NODE
temp;
temp
= (NODE) malloc(sizeof(struct BST));
temp->lchild
= NULL;
temp->rchild
= NULL;
return
temp;
}
void
insert(NODE , NODE );
int
max(int a, int b);
int
height(NODE root);
void insert(NODE root, NODE newnode)
{
/*Note: if newnode->data == root->data it will be skipped. No
duplicate nodes are allowed */
if
(newnode->data < root->data)
{
if
(root->lchild == NULL)
root->lchild
= newnode;
else
insert(root->lchild,
newnode);
}
if
(newnode->data > root->data)
{
if
(root->rchild == NULL)
root->rchild
= newnode;
else
insert(root->rchild,
newnode);
}
}
int max(int
a, int b)
{
return
(a>b)?a:b;
}
int height(NODE root)
{
if(root
== NULL)
return
0;
else
return
1
+ max( height(root->lchild), height(root->rchild) );
}
void main()
{
int val, i,n, ht;
NODE
root = NULL, newnode;
printf("\nEnter the
number of elements: ");
scanf("%d", &n);
for(i=1;i<=n;i++)
{
newnode
= get_node();
printf("\nEnter
The node value: ");
scanf("%d",
&val);
newnode->data =
val;
if
(root == NULL)
root
= newnode;
else
insert(root,
newnode);
}
ht = height(root);
printf("\nThe Height
of tree is: %d", ht);
}
Output:
Enter the number of elements: 12
Enter The node value: 6
Enter The node value: 9
Enter The node value: 5
Enter The node value: 2
Enter The node value: 8
Enter The node value: 15
Enter The node value: 24
Enter The node value: 14
Enter The node value: 7
Enter The node value: 8
Enter The node value: 5
Enter The node value: 2
The
Height of tree is: 4
No comments:
Post a Comment