## Wednesday, August 15, 2007

### Write a C program to create a mirror copy of a tree (left nodes become right and right nodes become left)!

This C code will create a new mirror copy tree.

mynode *copy(mynode *root)
{
mynode *temp;

if(root==NULL)return(NULL);

temp = (mynode *) malloc(sizeof(mynode));
temp->value = root->value;

temp->left = copy(root->right);
temp->right = copy(root->left);

return(temp);
}

This code will will only print the mirror of the tree

void tree_mirror(struct node* node)
{
struct node *temp;

if (node==NULL)
{
return;
}
else
{
tree_mirror(node->left);
tree_mirror(node->right);

// Swap the pointers in this node
temp = node->left;
node->left = node->right;
node->right = temp;
}
}

### Write a C program to compute the maximum depth in a tree?

int maxDepth(struct node* node)
{
if (node==NULL)
{
return(0);
}
else
{
int leftDepth = maxDepth(node->left);
int rightDepth = maxDepth(node->right);
if (leftDepth > rightDepth) return(leftDepth+1);
else return(rightDepth+1);
}
}

### Write a C program to find the mininum value in a binary search tree.

Here is some sample C code. The idea is to keep on moving till you hit the left most node in the tree

int minValue(struct node* node)
{
struct node* current = node;

while (current->left != NULL)
{
current = current->left;
}

return(current->data);
}

On similar lines, to find the maximum value, keep on moving till you hit the right most node of the tree.

### Write C code to determine if two trees are identical .

Here is a C program using recursion

int identical(struct node* a, struct node* b)
{
if (a==NULL && b==NULL){return(true);}
else if (a!=NULL && b!=NULL)
{
return(a->data == b->data &&
identical(a->left, b->left) &&
identical(a->right, b->right));
}
else return(false);
}

### Write a C program to delete a tree (i.e, free up its nodes)

Free up the nodes using Postorder traversal!.

### Write a C program to determine the number of elements (or size) in a tree.

int tree_size(struct node* node)
{
if (node==NULL)
{
return(0);
}
else
{
return(tree_size(node->left) + tree_size(node->right) + 1);
}
}

### Write a C program to find the depth or height of a tree.

Here is some C code to get the height of the three

tree_height(mynode *p)
{
if(p==NULL)return(0);
if(p->left){h1=tree_height(p->left);}
if(p=>right){h2=tree_height(p->right);}
return(max(h1,h2)+1);
}

The degree of the leaf is zero. The degree of a tree is the max of its element degrees. A binary tree of height n, h > 0, has at least h and at most (2^h -1) elements in it. The height of a binary tree that contains n, n>0, elements is at most n and atleast log(n+1) to the base 2.

Log(n+1) to the base 2 = h

n = (2^h - 1)