Binary tree – An introduction

0 / 1971 Binary Trees:

Today, in this blog we will discuss about binary trees. Binary tree is a data structure in which each node has two successors called the left and right child.

Below is a small image showing what a typical binary tree is like.

The above diagram just shows a binary tree which is different than a binary search tree. Difference between the two is the former is un-ordered and hence not fit for fast lookup of nodes however, binary search tree satisfies the criteria that if the child node is greater than the root, then it will be inserted to the right else to the left of the root node as shown in below diagram

Below is a small program that demonstrates creation of binary search tree and traversal , viz. inorder, preorder and postorder

C program for binary search tree

#include
#include

struct btree
{
int data;
struct btree *leftchild;
struct btree *rightchild;
};

void insert(struct btree **node, int data);
void inorder(struct btree *node);
void preorder(struct btree *node);
void postorder(struct btree *node);

int main()
{
int arr [] = {2,8,4,5,7,6,3};
int index = 0;

struct btree *root = NULL, *newNode = NULL;
int length = sizeof(arr)/sizeof(int);

for(index = 0; index < length; index++)
{
insert(&root, arr[index]);
}

printf("This is the output of inorder traversal :- \n");
inorder(root);
printf("\n");

printf("This is the output of inorder traversal :- \n");
preorder(root);
printf("\n");

printf("This is the output of inorder traversal :- \n");
postorder(root);
printf("\n");

return 0;
}

void insert(struct btree **node, int data)
{
if(*node == NULL)
{
*node = (struct btree *)malloc(sizeof(struct btree));
(*node)->data = data;
(*node)->leftchild = NULL;
(*node)->rightchild = NULL;
}
else
{
if(data > ((*node)->data))
insert(&(((*node)->rightchild)), data);
else
insert(&(((*node)->leftchild)), data);
}
}

void inorder(struct btree *node)
{
if(node != NULL)
{
inorder(node->leftchild);
printf("%d ", node->data);
inorder(node->rightchild);
}
}

void preorder(struct btree *node)
{
if(node != NULL)
{
printf("%d ", node->data);
inorder(node->leftchild);
inorder(node->rightchild);
}
}

void postorder(struct btree *node)
{
if(node != NULL)
{
inorder(node->leftchild);
inorder(node->rightchild);
printf("%d ", node->data);
}
}

The above program simply uses the recursive approach in creating and traversing through the binary search tree.

insert() inserts the node data passed as argument to the right if its greater than the root node else to the left by calling itself recursively. It first allocates memory for the root node, if the tree is empty.

inorder(), preorder() and postorder() all use recursion whereas, the traversing is done by visiting left, root and right in case of inorder,

root, left and right in case of preorder & left, right and root in case of post order.

Here is the output of the code: – Btree – Output

We will now move a bit ahead and write code for searching and deleting a particular node from a binary search tree. The below program , traverses through the tree, until node is found, frees the node so that there are no memory leaks and returns.

// code to search and delete a node from B search tree
/* CH8PR4.C: Program to insert and delete a node
from the binary search tree. */

#include
#include
#include

#define TRUE 1
#define FALSE 0

struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
} ;

void delete ( struct btreenode **, int ) ;
void search ( struct btreenode **, int, struct btreenode **,
struct btreenode **, int * ) ;

/* deletes a node from the binary search tree */
void delete ( struct btreenode **root, int num )
{
int found ;
struct btreenode *parent, *x, *xsucc ;

/* if tree is empty */
if ( *root == NULL )
{
printf ( "\nTree is empty" ) ;
return ;
}

parent = x = NULL ;

/* call to search function to find the node to be deleted */
search ( root, num, &parent, &x, &found ) ;

/* if the node to deleted is not found */
if ( found == FALSE )
{
printf ( "\nData to be deleted, not found" ) ;
return ;
}

/* if the node to be deleted has two children */
if ( x -> leftchild != NULL && x -> rightchild != NULL )
{
parent = x ;
xsucc = x -> rightchild ;

while ( xsucc -> leftchild != NULL )
{
parent = xsucc ;
xsucc = xsucc -> leftchild ;
}

x -> data = xsucc -> data ;
x = xsucc ;
}

/* if the node to be deleted has no child */
if ( x -> leftchild == NULL && x -> rightchild == NULL )
{
if ( parent -> rightchild == x )
parent -> rightchild = NULL ;
else
parent -> leftchild = NULL ;

free ( x ) ;
return ;
}

/* if the node to be deleted has only rightchild */
if ( x -> leftchild == NULL && x -> rightchild != NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> rightchild ;
else
parent -> rightchild = x -> rightchild ;

free ( x ) ;
return ;
}

/* if the node to be deleted has only left child */
if ( x -> leftchild != NULL && x -> rightchild == NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> leftchild ;
else
parent -> rightchild = x -> leftchild ;

free ( x ) ;
return ;
}
}

/*returns the address of the node to be deleted, address of its parent and
whether the node is found or not */
void search ( struct btreenode **root, int num, struct btreenode **par, struct
btreenode **x, int *found )
{
struct btreenode *q ;

q = *root ;
*found = FALSE ;
*par = NULL ;

while ( q != NULL )
{
/* if the node to be deleted is found */
if ( q -> data == num )
{
*found = TRUE ;
*x = q ;
return ;
}

*par = q ;

if ( q -> data > num )
q = q -> leftchild ;
else
q = q -> rightchild ;
}
}

Stay tuned for more interesting programming stuff.