C++ Program to count the Height of Binary Search Tree
Description:
This is a Program to count the Height of Binary Search Tree.
The approach will be as follow::
First, we will Construct the Binary Search Tree and insert some nodes
create the following tree
95
/ \
55 110
/ \ / \
40 75 100 150
95
/ \
55 110
/ \ / \
40 75 100 150
After Consrtucting this BST we can observe the nodes
0 Degree nodes -> 40, 75, 100, 150
1 Degree nodes -> No nodes
2 Degree nodes -> 95 55 110
Height of Tree is -> 3
So the Program is to count the Height of this Binary Search Tree
LOGIC::
we will Recursively Call our helper function on root's left subtree and root's
right subtree.
And return the greater value among them.
Here is the sample code for more clarification.
C++ CODE
//Program to count the Height of Binary Search Tree
using namespace std;
struct node
{
int data;
struct node *left, *right;
};
//Prototypes
struct node *add_node(struct node *, int);
struct node *create_node(int);
void in_order(struct node *);
int height(struct node *root)
{
if (!root)
return 0;
int x = height(root->left);
int y = height(root->right);
return (x > y) ? x += 1 : y += 1;
}
int main()
{
struct node *root = nullptr;
root = add_node(root, 50);
add_node(root, 30);
add_node(root, 20);
add_node(root, 40);
add_node(root, 70);
add_node(root, 60);
add_node(root, 80);
cout << "\nIN_ORDER :: ";
in_order(root);
cout << endl;
cout << "\nHeight of the tree is :: " << height(root) << endl;
return 0;
}
struct node *create_node(int key)
{
struct node *ptr = (struct node *)malloc(sizeof(struct node));
ptr->data = key;
ptr->left = ptr->right = NULL;
return ptr;
}
struct node *add_node(struct node *root, int key)
{
if (!root)
return create_node(key);
//------------ locate the insertion --------------------
if (key < root->data)
root->left = add_node(root->left, key);
else
root->right = add_node(root->right, key);
return root;
}
void in_order(struct node *root)
{
if (root)
{
in_order(root->left);
cout << root->data << " ";
in_order(root->right);
}
}
Here is the Output
Comments