## 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)

### Write your own trim() or squeeze() function to remove the spaces from a string.

#include < stdio.h >

char *trim(char *s);

int main(int argc, char *argv[])
{
char str1[]=" Hello I am Good ";
printf("\n\nBefore trimming : [%s]", str1);
printf("\n\nAfter trimming : [%s]", trim(str1));

getch();
}

// The trim() function...

char *trim(char *s)
{
char *p, *ps;

for (ps = p = s; *s != '\0'; s++)
{
if (!isspace(*s))
{
*p++ = *s;
}
}

*p = '\0';

return(ps);
}

And here is the output...

Before trimming : [ Hello I am Good ]
After trimming : [HelloIamGood]

Another version of this question requires one to reduce multiple spaces, tabs etc to single spaces...

### How to add two numbers without using the plus operator?

Actually,

SUM = A XOR B
CARRY = A AND B

On a wicked note, you can add two numbers wihtout using the + operator as follows

a - (- b)

### How to generate prime numbers? How to generate the next prime after a given prime?

This is a very vast subject. There are numerous methods to generate primes or to find out if a given number is a prime number or not. Here are a few of them. I strongly recommend you to search on the Internet for more elaborate information.

Brute Force
Test each number starting with 2 and continuing up to the number of primes we want to generate. We divide each numbr by all divisors upto the square root of that number. If no factors are found, its a prime.

Using only primes as divisors
Test each candidate only with numbers that have been already proven to be prime. To do so, keep a list of already found primes (probably using an array, a file or bit fields).

Test with odd candidates only
We need not test even candidates at all. We could make 2 a special case and just print it, not include it in the list of primes and start our candidate search with 3 and increment by 2 instead of one everytime.

Table method
Suppose we want to find all the primes between 1 and 64. We write out a table of these numbers, and proceed as follows. 2 is the first integer greater than 1, so its obviously prime. We now cross out all multiples of two. The next number we haven't crossed out is 3. We circle it and cross out all its multiples. The next non-crossed number is 5, sp we circle it and cross all its mutiples. We only have to do this for all numbers less than the square root of our upper limit, since any composite in the table must have atleast one factor less than the square root of the upper limit. Whats left after this process of elimination is all the prime numbers between 1 and 64.

### Write a program to print numbers from 1 to 100 without using loops!

Another "Yeah, I am a jerk, kick me! kind of a question. I simply dont know why they ask these questions.

Nevertheless, for the benefit of mankind...

Method1 (Using recursion)

void printUp(int startNumber, int endNumber)
{
if (startNumber > endNumber)
return;

printf("[%d]\n", startNumber++);
printUp(startNumber, endNumber);
}

Method2 (Using goto)

void printUp(int startNumber, int endNumber)
{
start:

if (startNumber > endNumber)
{
goto end;
}
else
{
printf("[%d]\n", startNumber++);
goto start;
}

end:
return;
}