C C++ Java Data Structure Python JavaScript CSS Ajax PL/SQL PHP Puzzles C programs C++ programs Java programs

Home » Data Structure

Find Height (Maximum Depth) of a Binary Search Tree (C++ program)

Learn: How to find the height or maximum depth of a binary search tree? This article includes definition, algorithm and implementation in C++ program.
Submitted by Abhishek Jain, on July 30, 2017

The Height (or depth) of a tree is defined to be the maximum level of any node in the tree. Some authors define depth of a node to be the length of the longest path from the root node to that node, which yields the relation:

Depth of the tree = Height of the tree - 1

Height of BST (Binary Search Tree)

Reference: http://codersmaze.com/data-structure-explanations/trees-in-data-structure/

Algorithm:

FindHeight( Node root)
	If root=NULL 
		return 0
	Else
	int l=FindHeight (root->left)
	int r=FindHeight(root->right) 
	Return max(l,r)+1
	[End If]
[End]
Height of BST (Binary Search Tree)

Consider the program:

#include<iostream>
using namespace std;

struct node
{
	int data;
	node* left;
	node* right;
};

struct node* getNode(int data)
{
	node* newNode=new node();
	newNode->data=data;
	newNode->left=NULL;
	newNode->right=NULL;
	return newNode;
}

void inorder(struct node* root)
{
    if (root != NULL)
     {
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

struct node* Insert(struct node* root, int data)
{
	if (root == NULL)
		return getNode(data);

	if (data < root->data)
		root->left  = Insert(root->left, data);
	else if (data > root->data)
		root->right = Insert(root->right, data);

	return root;
}

int main()
{  
	node* root=NULL;
	root=Insert(root,20);
	Insert(root,15);
	Insert(root,25);
	Insert(root,18);
	Insert(root,10);
	Insert(root,16);
	Insert(root,19);
	cout<<"Before Insertion: ";
	cout<<"\nInorder: ";
	inorder(root);
	cout<<endl;

	root=Insert(root,17);
	cout<<"\nNode Inserted"<<endl;

	cout<<"\nAfter Insertion: ";
	cout<<"\nInorder: ";
	inorder(root);
	cout<<endl;

	return 0;
}

Output

Inorder: 14579
Height of the tree is 3
Max. Depth of the tree is 2








COMMENTS