Programming Trees

Trees are an important data structure (I had to say this else this post won’t make sense 😛 ). All of us come around questions based on trees and I am talking about algorithm problems, not just simple ones which are hardly 5-10 lines of code. Every time I had to solve a problem based in trees I had to go through the process of coding all the basic routines for a tree. Frustrated by this I went on to make a huge file which practically has all the routines which are basic to trees. Above that I made two versions of all the codes i.e. iterative and recursive ones (see my frustration level :D). Anyways, now that I have made it, it is very easy for me to write a program for trees. Just copy the required routines from that file and write my algorithm. I just thought of sharing that file with all you guys, so that you might not repeat the same thing :). The list of all the routines implemented is below:

1. Create mirror image of a tree
2. Insert (recursive & iterative)
3. Find element (recursive & iterative)
4. Find Min/Max (recursive & iterative)
5. Check if a tree is BST
6. Delete an element (recursive & iterative)
7. In/pre/post order traversals (recursive & iterative)
8. Level Order traversal
9. Height of tree
10.Check if the tree is balanced
11.Size (no. of elements) in tree
12.Find Median of tree (without globals and static variables)

Here is the code

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

#define DATA int

#define INT    "%d"
#define FLOAT  "%f"
#define CHAR   "%c"
#define DOUBLE "%lf"

#ifdef DATA
#define SCAN INT
#endif

typedef struct tree_node
{
	DATA data;
	struct tree_node *left;
	struct tree_node *right;
}node;

node * mirror(node *root)
{
	if (root == NULL)
		return root;
	node *tmp  = (node *)malloc(sizeof(node));
	tmp->data  = root->data;
	tmp->left  = mirror(root->right);
	tmp->right = mirror(root->left);
	return tmp;
}

int isBST(node *root);

void insert_recur(node **root, DATA n)
{
	if (*root == NULL)
	{
		node *tmp = (node *)malloc(sizeof(node));
		tmp->data = n;tmp->left=tmp->right=NULL;
		*root = tmp;
		return ;
	}
	if ((*root)->data < n )
		insert_recur(&((*root)->right),n);
	else if ((*root)->data > n )
		insert_recur(&((*root)->left),n);
	return ;
}

void insert_iter(node **root, DATA n)
{
	node *tmp  = (node *)malloc(sizeof(node));
	tmp->data = n;tmp->left = tmp->right = NULL;
	if (*root == NULL)
	{
		*root = tmp;
		return ;
	}
	node *ptr; ptr = *root;
	while (1)
	{
		if (ptr->data < n)
		{
			if (ptr->right)
				ptr = ptr->right;
			else
			{
				ptr->right = tmp;
				return ;
			}
		}
		else if (ptr->data > n )
		{
			if (ptr->left)
				ptr = ptr->left;
			else
			{
				ptr->left = tmp;
				return ;
			}
		}
		else
			return ;
	}
	return ;
}

node *find_recur(node *start,DATA n)
{
	if (start == NULL)
		return NULL;
	if (start->data == n)
		return start;
	else if (start->data > n )
		return find_recur(start->left,n);
	else
		return find_recur(start->right,n);
}

node *find_iter(node *start,DATA n)
{
	if (start == NULL)
		return NULL;
	while (start)
	{
		if (start->data == n)
			break;
		else if (start->data > n)
			start = start->left;
		else
			start = start->right;
	}
	return start;
}

node *find_min_iter(node *start)
{
	if (start == NULL)
		return start;
	while (start->left)
		start = start->left;
	return start;
}

node *find_min_recur(node *start)
{
	if (start->left == NULL)
		return start;
	return find_min_recur(start->left);
}

node *find_max_iter(node *start)
{
	if (start == NULL)
		return start;
	while (start->right)
		start = start->right;
	return start;
}

node *find_max_recur(node *start)
{
	if (start->right == NULL)
		return start;
	return find_max_recur(start->right);
}

int myisBST(node *start, int min, int max)
{
		if (start == NULL)
			return 1;
		if (start->data <= min || start->data >= max)
			return 0;
		return myisBST(start->left,min,start->data-1) \
		 && myisBST(start->right,start->data+1,max);
}

int isBST(node *start)
{
	if (start == NULL)
		return 1;
	return myisBST(start->left,find_min_iter(start)->data-1,start->data-1) \
	&& myisBST(start->right,start->data+1,find_max_iter(start)->data+1);
}

void delete_iter(node **root, DATA n)
{
	// Too lazy to implement this one ..
}

void delete_recur(node **root, DATA n)
{
	if ( *root == NULL )
		return ;
	if ( (*root)->data == n ) {  // delete the root
		node *t = find_max_iter((*root)->left);
		if ( t == NULL ) {
			t = find_min_iter((*root)->right);
			if ( t == NULL ) {
				*root = NULL;
				return ;
			}
		}
		int var = t->data;
		delete_recur(root,var);
		(*root)->data = var ;
		return ;
	}
	if ((*root)->left && ((*root)->left)->data == n ) {
		node *tmp = (*root)->left;
		if ( tmp->left && tmp->right ) {
			int val = find_max_iter(tmp->left)->data;
			delete_recur(&(tmp->left),val);
			tmp->data = val;
		}
		else {
			(*root)->left = tmp->left!=NULL?tmp->left:tmp->right;
			free(tmp);
		}
	}
	else if ( (*root)->right && ((*root)->right)->data == n ) {
		node *tmp = (*root)->right;
		if (tmp->left && tmp->right) {
			int val = find_min_iter(tmp->right)->data;
			delete_recur(&(tmp->right),val);
			tmp->data = val;
		}
		else {
			(*root)->right = tmp->left!=NULL?tmp->left:tmp->right;
			free(tmp);
		}
	}
	else if ( (*root)->data < n ) 
		delete_recur(&((*root)->right),n);
	else
		delete_recur(&((*root)->left),n);
	return ;
}

void inorder(node *root)
{
	if (root == NULL)
		return ;
	inorder(root->left);
	printf("%d ",root->data);
	inorder(root->right);
	return ;
}

void preorder(node *start)
{
	if (start == NULL)
		return ;
	printf("%d ",start->data);
	preorder(start->left);
	preorder(start->right);
	return ;
}

void postorder(node *start)
{
	if (start == NULL)
		return ;
	postorder(start->left);
	postorder(start->right);
	printf("%d ",start->data);
	return;
}

typedef struct LL
{
	DATA data;
	struct LL *next;
        node *left, *right;
}ll;

void levelorder(node * start)
{
	ll *L_end, *tmp1, *tmp, *t;

	tmp = (ll *)malloc(sizeof(ll));
	tmp->data = INT_MIN;tmp->next = NULL;

	t = (ll *)malloc(sizeof(ll));
	t->data = start->data;
	t->left = start->left;t->right = start->right;t->next = tmp;

	tmp1 = t;L_end = tmp;
	int len = 1, ii=1;
	printf("\n");
	while (len > 0) {
		while (len > 0 && tmp1 != NULL && tmp1->data != INT_MIN) {
			printf("%d -> ",tmp1->data);
			len--;
			if (tmp1->left) {
				len++;
				ll * tmp2 = (ll *)malloc(sizeof(ll));
				tmp2->data = (tmp1->left)->data;
				tmp2->left = (tmp1->left)->left;
				tmp2->right = (tmp1->left)->right;
				tmp2->next = NULL;
				L_end->next = tmp2;L_end = tmp2;
			}
			if (tmp1->right) {
				len++;
				ll * tmp2 = (ll *)malloc(sizeof(ll));
				tmp2->data = (tmp1->right)->data;
				tmp2->left = (tmp1->right)->left;
				tmp2->right = (tmp1->right)->right;
				tmp2->next = NULL;
				L_end->next = tmp2;L_end = tmp2;
			}
			ll * tt = tmp1;
			tmp1= tmp1->next;
			tt->next = NULL;free(tt);
		}
		printf(" Level No. %d\n",ii++);
		L_end->next = tmp1;
		if (tmp1 == NULL)
			break;
		ll *t1 = tmp;
		tmp1 = tmp1->next;
		t1->next = NULL;
		L_end = t1;
	}
	return ;
}

int height(node *root)
{
	if (root == NULL)
		return 0;
	int h_l = 1 + height(root->left);
	int h_r = 1 + height(root->right);
	return h_l > h_r ? h_l : h_r ;
}

int isBalanced(node *root)
{
	if (root == NULL)
		return 0;

	int ret = isBalanced(root->left);
	if (ret == 0)
	{
		int h_l = height(root->left), h_r = height(root->right);
		if (h_l - h_r != 0)
			return 1;
		else
			ret = 0;
		isBalanced(root->right);
	}
	return ret;
}

int size(node *root)
{
    if (root == NULL )
        return 0;
    if (root->left && root->right)
        return size(root->left) + size(root->right) + 1;
    else if (!root->left && root->right)
        return size(root->right) + 1;
    else if (root->left && !root->right)
        return size(root->left) + 1;
    else
        return 1;
}

void myMedian(node *root, int *m1, int *m2, int *c, int *sum)
{
    if (root == NULL)
        return ;
    if (*m1 > 0 || *m2 > 0 )
        myMedian(root->left, m1, m2, c, sum);
    (*c)++;
    if (*c == *m1 )
    {
        *m1 = -1;
        *sum = root->data;
    }
    if (*c == *m2)
    {
        *m2 = -1;
        (*sum)+= root->data;
        *(sum)/=2;
        return ;
    }
    if (*m1 > -1 || *m2 > -1 )
        myMedian(root->right, m1, m2, c, sum);
    return ;
}

int findMedian(node *root)
{
    int numelmnts = size(root), m1 = numelmnts >> 1, m2 = -1, c=0, sum =0;
    if (numelmnts & 1)
        m1++;
    else
        m2 = m1 + 1;
    myMedian(root, &m1, &m2, &c, &sum);
    return sum;
}

int main()
{
	node *root = NULL;
	DATA r;
	char ch;
	printf("Enter the root element of the tree :");
	scanf(SCAN,&r);
	insert_recur(&root,r);
	printf(" Start Operations : \n \t Enter i -1 to stop the program\n");
	while (1)
	{
		printf("\tEnter Command : ");
		scanf(" %c",&ch);
		if (ch == 'i') //insert
		{
			scanf(SCAN,&r);
			if (r == -1)
				break;
			insert_recur(&root,r);
			continue;
		}
		if (ch == 'd') // delete
		{
			scanf(SCAN,&r);
			delete_recur(&root,r);
			continue;
		}
		if (ch =='p')
		{
			char tmp1[100];
			scanf("%s",tmp1);
			if (tmp1[1]=='e')
			{
				printf("\tLevel Order Traversal\n");
				levelorder(root);
			}
			if (tmp1[1]=='n')
			{
				printf("\tInorder Traversal \n");
				inorder(root);
			}
			else if (tmp1[1] == 'o')
			{
				printf("\tPostorder Traversal \n");
				postorder(root);
			}
			else if (tmp1[1] == 'r')
			{
				printf("\tPreorder Traversal \n");
				preorder(root);
			}
			printf("\n");
			continue;
		}
	}
	printf("isBST      : %d\n",isBST(root));
	printf("\nMedian of elements : %d\n",findMedian(root));
	printf("\n\tProgram Complete\n");
	return 0;
}

I liked this concept of my own and made a similar file for linked list also :P, but it does not have many routines so will post it same time late. Hope this makes some of your tasks easier :D.

Advertisements
%d bloggers like this: