Binary Tree – Inserting a Node

If the binary search tree is initially empty, then the element is inserted as a root node. Otherwise the element is inserted as terminal node. If the element is less than the element in the root node, then the element is inserted in the left sub tree else to the right sub tree.

void insertelement(BST *tree, int element) { BST *ptr,*nodeptr,*parentptr; ptr = (BST*)malloc(sizeof(BST)); ptr->info = element; ptr->left = ptr->right = NULL; if(tree == NULL) *tree = ptr; else { parentptr = NULL; nodeptr = *tree; while(nodeptr != NULL) { parentptr = nodeptr; if(element < nodeptr->info) nodeptr = nodeptr->left; else nodeptr = nodeptr->right; } if(element < parentptr->info) parentptr->left = ptr; else parentptr->right = ptr; } }

Determining the Height of a Binary Tree

We find the height of the left sub tree and right sub tree of a given node. The height of a binary tree at a given node will be equal to maximum height of the left and right sub tree plus 1.The program given below illustrates the implementation of various steps required,

int height(BST *tree) { int lheight, rheight; if(tree == NULL) { return 0; } else { lheight = height(tree->left); rheight = height(tree->right); if(lheight > rheight) return ++lheight; else return ++rheight; } }

Calculating Total Number of Nodes

Any of the traversal schemes or algorithm can be used to determine the number of elements present in the tree.

The approach we use is:

Number of elements in the tree is equal to number of nodes in left sub tree plus number of nodes in right sub tree plus one.

int totalnodes(BST *tree) { if(tree==NULL) return 0; else return (totalnodes(tree->left) + totalnodes(tree->right) + 1); }

Complete program illustrating insertion and traversal in Binary Search Tree

#include <iostream.h> #include <malloc.h> #include<process.h> #include<conio.h> struct node { int info; node *lchild; node *rchild; }*root; void display(node *,int ); void postorder(node *); void inorder(node *); void preorder(node *); void case_c(node *,node *); void case_b(node *,node *); void case_a(node *,node *); void insert(int ); void main() { int choice,num; root=NULL; while(1) { getch(); clrscr(); cout<<"n"; cout<<"1.Insertn"; cout<<"2.Inorder Traversaln"; cout<<"3.Preorder Traversaln"; cout<<"4.Postorder Traversaln"; cout<<"5.Displayn"; cout<<"6.Quitn"; cout<<"Enter your choice : "; cin>>choice; switch(choice) { case 1: cout<<"Enter the number to be inserted : "; cin>>num; insert(num); break; case 2: inorder(root); break; case 3: preorder(root); break; case 4: postorder(root); break; case 5: display(root,1); break; case 6: exit(0); default: cout<<"Wrong choicen"; } } } void find(int item,node **par,node **loc) { node *ptr,*ptrsave; if(root==NULL) /*tree empty*/ { *loc=NULL; *par=NULL; return; } if(item==root->info) /*item is at root*/ { *loc=root; *par=NULL; return; } /*Initialize ptr and ptrsave*/ if(item<root->info) ptr=root->lchild; else ptr=root->rchild; ptrsave=root; while(ptr!=NULL) { if(item==ptr->info) { *loc=ptr; *par=ptrsave; return; } ptrsave=ptr; if(item<ptr->info) ptr=ptr->lchild; else ptr=ptr->rchild; }/*End of while */ *loc=NULL; /*item not found*/ *par=ptrsave; }/*End of find()*/ void insertint item) { struct node *tmp,*parent,*location; find(item,&parent,&location); if(location!=NULL) { cout<<"Item already present"; return; } tmp=(node *)malloc(sizeof(node)); tmp->info=item; tmp->lchild=NULL; tmp->rchild=NULL; if(parent==NULL) root=tmp; else if(item<parent->info) parent->lchild=tmp; else parent->rchild=tmp; }/*End of insert()*/ void case_a(node *par,node *loc ) { if(par==NULL) /*item to be deleted is root node*/ root=NULL; else if(loc==par->lchild) par->lchild=NULL; else par->rchild=NULL; }/*End of case_a()*/ void case_b(node *par,node *loc) { node *child; /*Initialize child*/ if(loc->lchild!=NULL) /*item to be deleted has lchild */ child=loc->lchild; else /*item to be deleted has rchild */ child=loc->rchild; if(par==NULL ) /*Item to be deleted is root node*/ root=child; else if( loc==par->lchild) /*item is lchild of its parent*/ par->lchild=child; else /*item is rchild of its parent*/ par->rchild=child; }/*End of case_b()*/ void case_c(node *par,node *loc) { node *ptr,*ptrsave,*suc,*parsuc; /*Find inorder successor and its parent*/ ptrsave=loc; ptr=loc->rchild; while(ptr->lchild!=NULL) { ptrsave=ptr; ptr=ptr->lchild; } suc=ptr; parsuc=ptrsave; if(suc->lchild==NULL && suc->rchild==NULL) case_a(parsuc,suc); else case_b(parsuc,suc); if(par==NULL) /*if item to be deleted is root node */ root=suc; else if(loc==par->lchild) par->lchild=suc; else par->rchild=suc; suc->lchild=loc->lchild; suc->rchild=loc->rchild; }/*End of case_c()*/ void preorder(node *ptr) { if(root==NULL) { cout<<"Tree is empty"; return; } if(ptr!=NULL) { cout<<ptr->info; preorder(ptr->lchild); preorder(ptr->rchild); } }/*End of preorder()*/ void inorder(node *ptr) { if(root==NULL) { cout<<"Tree is empty"; return; } if(ptr!=NULL) { inorder(ptr->lchild); cout<<ptr->info; inorder(ptr->rchild); } }/*End of inorder()*/ void postorder(node *ptr) { if(root==NULL) { cout<<"Tree is empty"; return; } if(ptr!=NULL) { postorder(ptr->lchild); postorder(ptr->rchild); cout<<ptr->info; } }/*End of postorder()*/ void display(node *ptr,int level) { int i; if ( ptr!=NULL ) { display(ptr->rchild, level+1); cout<<"n"; for (i = 0; i < level; i++) cout<<" "; cout<<ptr->info; display(ptr->lchild, level+1); } }/*End of display()*/