Height of a Binary Search Tree - data structure tutorial

Prerequisites

Please refer to my previous posts on binary trees before reading about Height of a Binary Search Tree - data structure tutorial.

A lot of question are asked about height and depth of Tree in Interviews and I have seen many people having trouble in distinguishing between depth and height of a Tree. So, today we gonna move ahead and learn what is height of a tree, how is it different from depth and how we will implement it in a c++ program. So, let's start:

What does it mean by height of a tree?

Height of a tree is the longest distance from root of a tree to the leaf node. Let's take an example to understand it clearly.
In the tree below, there are 4 leaf nodes namely 4, 8, 9 and 7 but from root node 1 then farthest lead node is 9 ,thus the height of the tree will be number of edges between 1 and 9 which is 3.

Then what's the difference between height and depth of a Tree?

We often confuse with height and depth of a tree. But ,these 2 have different meanings.
Depth is basically distance of a node from root. Let's take an example to understand it clearly.
Depth of node 2 is is the number of edges between root and node 2 which is 1 thus Depth of node 2 is 1.
Depth of node 7 is number of edges between root node and node 7 which is 2.

I hope now you can differentiate between height and depth.

Logic to find height of a Tree

We will take a function find_height() which will have one parameter root.The logic is pretty straightforward.We will find height of left subtree and height of right subtree and the greater of the 2 heights + 1 will be the height of our tree. We will add +1 for the edge connecting subtree to the root.

We will find height of left subtree and right subtree using recursion. For recursion we need a base condition so , we will take base condition like if(root==NULL) return -1 and it makes sense because a empty tree will have -1 as height.
Otherwise if the tree is not empty then we will call left subtree by
left_height = find_height(root->left)
The height of left subtree will be stored in left_height.
Then, we will make a call to right subtree by
right_height = find_height(root->right)
The height of right subtree will be stored in right_height.
After this, we will return max(left_height, right_height)+1.

NOTE: Some people find height by counting the number of nodes from root to leaf but we are finding height of the tree by counting number of edges from root to leaf.

C++ implementation to find Height of the Tree

#include<iostream>
using namespace std;

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

int findheight(bstnode* root)
{
    if(root==NULL)
        return -1;
    return max(findheight(root->left),findheight(root->right))+1;
}

bstnode* getnewnode(int data)
{
    bstnode* newnode=new bstnode();
    newnode->data=data;
    newnode->left=NULL;
    newnode->right=NULL;
    return newnode;
}

bstnode* insert(bstnode* root,int data)
{
    if(root==NULL)
    {
        root=getnewnode(data);
    }
    else if(root->data>=data)
    {
        root->left=insert(root->left,data);
    }
    else
    {
        root->right=insert(root->right,data);
    }
    return root;
}


int main()
{
    bstnode* root=NULL;
    root=insert(root,15);
    root=insert(root,10);
    root=insert(root,20);
    root=insert(root,25);
    root=insert(root,8);
    root=insert(root,12);
    cout<<"tree in the memory is as follow:"<<endl;
    cout<<"               15               "<<endl;
    cout<<"              /  \\              "<<endl;
    cout<<"            10    20            "<<endl;
    cout<<"           /  \\    \\           "<<endl;
    cout<<"          8    12   25         "<<endl;
    cout<<endl;
    cout<<"height of tree is: ";
    cout<<findheight(root);
    return 0;
}

OUTPUT:

This was all about Height of a Binary Search Tree - data structure tutorial. In the next post we will learn how to delete a node from a Binary Tree.

Height of a Binary Search Tree - data structure tutorial

Contact Form