Binary Search Tree | Hight Of A Tree

Path:

The path from node N₁ to node N_k is a sequence of nodes N₁, N₂, …, N_k where N_i is the parent of N_i+1. The length of the path is the number of nodes in the path.

     3
    / \
   1   4
  / \   \
 0   2   5

3 -> 1 -> 1 is path with 3 nodes.

Hight Of A Node:

Hight of a node N is the longest path from the node N to a leaf node (a node with no child). Hight of a leaf node is 0.

     3
    / \
   1   4
  / \   \
 0   2   5

Hight(node(1)) = length(1->0) = 2

Hight Of A Tree:

Hight of a tree T is the hight of its root node.

     3
    / \
   1   4
  / \   \
 0   2   5

Hight(node(3)) = length(3->1->0) = 3

C Program

#include <stdio.h>
#include <stdlib.h>

typedef struct BST
{
   struct BST *lc, *rc;
   int data;
}BST;

void inorder(BST *t)
{
    if(t != NULL) {
        inorder(t->lc);
        printf("%d ",t->data);
        inorder(t->rc);
    }
}

BST *insertNode(BST *T,int item)
{
    BST *curr = T,*prev = NULL,*temp = NULL;
    int found = 0;
    //Search for the proper position of the node to insert...
    while(curr != NULL && !found)
    {
        //Keeping track of the previous node...
        prev = curr; 
        // If item already exists...
        if(curr->data == item) 
        {
            found = 1;
            printf("\nItem %d Already Exists In The BST.\n",item);
        }
        else if(curr->data > item) {
            curr = curr->lc;
        }
        else {
            curr = curr->rc;
        }
    }
    //Creating a new node...
    temp = (BST*)malloc(sizeof(BST));
    temp->data = item;
    temp->lc = NULL;
    temp->rc = NULL;
    //Only for first node or time...
    if(T == NULL)
        T = temp;
    else if(item > prev->data)
        prev->rc = temp;
    else
        prev->lc = temp;
    return T;
}

int max(int a, int b) { return ((a > b)? a : b); }

int hightOfTree(BST *T)
{
    if (T == NULL)
        return 0;
    else
    {
        return (1 + max(hightOfTree(T->lc), hightOfTree(T->rc)));
    }
}

int main()
{
    BST *T = NULL;
    int value;
    
    printf("Enter Values In BST:\n");
    scanf("%d",&value);
    while (value != -999) {
        T = insertNode(T, value);
        scanf("%d",&value);
    }
    
    inorder(T);
    printf("\nHight Of Tree Is: %d.",hightOfTree(T));
    return 0;
}

Output

Enter Values In BST:
3 1 2 0 4 -999
0 1 2 3 4 
Hight Of Tree Is: 3.

Enter Values In BST:
5 4 3 2 1 -999
1 2 3 4 5 
Hight Of Tree Is: 5.

Running Time

This algorithm takes time proportional to the number of nodes in the tree i.e. O(n).