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 FindHeight(node* root)
{
	if(root==NULL)
		return 0;

	else
	{
		int lb=FindHeight(root->left);
		int rb=FindHeight(root->right);
		return max(lb,rb)+1;
	}
}
int main()
{
	node* root=NULL;
	root=Insert(root,7);
	Insert(root,9);
	Insert(root,4);
	Insert(root,1);
	Insert(root,5);

	cout<<"Inorder: ";
	inorder(root);
	cout<<endl;

	cout<<"Height of the tree is "<<FindHeight(root)<<endl;
	cout<<"Max. Depth of the tree is "<<FindHeight(root)-1;
	
	return 0;
}

Output

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





Was this page helpful? YES NO

Are you a blogger? Join our Blogging forum.



Comments and Discussions


We are using Google to publish ads on our website; Google has its own privacy policies. They may save log, cookies on your system. Google may also collect information of your system like IP address, region, city, country. For more details please go through the Google’s privacy policy.