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

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

10 Responses to Programming Trees

  1. spsneo says:

    Great work again!
    I can also contribute in such tasks.

  2. Neet says:

    Is printing tree vertically same as print level order ( assuming we add a new line for every new level)

    Also a few more interesting questions

    1. inverting a tree ( reverse a tree)
    2. finding inorder successor with parent pointer given
    3. Finding LCA of 2 nodes in n-ary tree

    Have you tried writing the code to merge to BSTs

    • Avi Dullu says:

      Printing the tree vertically is completely different from Level order printing. IN vertical printing, you also have to show the parent child links, whereas in level order, only nodes at same level have to be printed.

      1. I’m not clear as to what ‘reversing’ means, please elaborate.
      2. This question is already discussed by spsneo here
      3. Its a very common problem, you need to find the paths from root, to both the nodes and just find the common path starting from root in both of them.

      Merging two BST is better done by writing the in order traversals of both the trees, merging them (because both are sorted) and then constructing a tree from the merged sequence. It is an O(n) method. I don’t think the code will be too complex. 🙂

  3. Neet says:

    1. Have you tried the vertical tree printing? can you help me

    2. Inverting tree, the child nodes ( left / right) point back to the root. Am I clear now?

    3. Merging BSTs with extra space is easy. How about not using that extra space to merge them and reconstruct.

    • Avi Dullu says:

      1. In vertical tree printing, only thing to be found out is the displacement of the root from the leftmost node. This can be found out in 1 inorder traversal. (think how 🙂 )

      2. This can also be done in a single inorder traversal, just pass the parent pointer in the recursion and figure when the children pointers needs to be updated.

      3. yes, merging with extra space is easy but is O(n). Another ways are, first method, to convert both trees into doubly linked lists (in place) and merge them and again build a tree out of the linked list. O(n logn). second method, keep inserting each element from one tree into the other. O(n logn ).

  4. Neet says:

    Why dont you add a chat service to your website. will help people like me with your free service on algos:)

  5. Neet says:

    For the vertical tree,

    can you give me an example.

    • Avi Dullu says:

      The formatting is causing a problem so I shall give the tree in bracket form. ( (.) means a NULL) )

      (A (B (D (.) (.) ) (E (G (J (M (.) (.) ) (N (.) (.) ) ) (.) ) (H (.) (K (.) (O (.) (.) ) ) ) ) ) (C (F (I (L (.) (.) ) (.) ) (.) ) (.) ) )

      In this tree, you need to find out the distance of rightmost node in left subtree and leftmost node in right subtree of the root then put spaces accordingly. eg. B has to be put 5 nodes away from A because E,H,K and O need to be put in middle similarly C has been put 4 nodes away because of (F,I,L).

      The idea simply is that, each node should have its right subtree entirely to its right i.e. the leftmost node of right subtree will be below it and rightmost node of left subtree will also be below it , on opposite sides. Here the leftmost node of right subtree is 3 units away and rightmost node of left subtree of A is 4 units away. After placing A, recurse on the process for its children.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: