Traverese tree in PostOrder

/*
Given a binary tree, print its
nodes according to the "bottom-up"
postorder traversal.
*/
void printPostorder(struct node* node) {
if (node == NULL) return;
// first recur on both subtrees
printTree(node->left);
printTree(node->right);
// then deal with the node
printf("%d ", node->data);
}

Check if a binary tree is a binary search tree

int isBST(struct node* node) {

if (node==NULL) return(true);
// false if the min of the left is > than us
if (node->left!=NULL && minValue(node->left) > node->data)
return(false);
// false if the max of the right is <= than us
if (node->right!=NULL && maxValue(node->right) <= node->data)
return(false);
// false if, recursively, the left or right is not a BST
if (!isBST(node->left) || !isBST(node->right))
return(false);
// passing all that, it's a BST
return(true);
}


int isBST2(struct node* node) {
return(isBSTUtil(node, INT_MIN, INT_MAX));
}
/*
Returns true if the given tree is a BST and its
values are >= min and <= max.
*/
int isBSTUtil(struct node* node, int min, int max) {
if (node==NULL) return(true);
// false if this node violates the min/max constraint
if (node->datadata>max) return(false);
// otherwise check the subtrees recursively,
// tightening the min or max constraint
return
isBSTUtil(node->left, min, node->data) &&
isBSTUtil(node->right, node->data+1, max)
);
}

Technique for Swapping Two Integers Without Using a Temporary variable

There's another version of this solution that applies to integral values only.
void swap(int& i, int& j)
{
i ^= j;
j ^= i;
i ^= j;
}// i and j are swapped
You can apply this technique to any integral type, e.g., char, short, unsigned long, but not to floating-point variables.

write an O(log2(N)) algorithm to find X^N

________________________________________

int Sq(int x, int n) {
int y = 0;

if (n < 0) return -1;
if (n == 0) return 1;
if (n == 1) return x;

if (n % 2 == 0) {
y = Sq(x, n/2);
return y * y;
}

y = Sq(x, n/2);
return x * y * y;
}

Classis Factorial problem & Solution..

One of the classic examples of using recursion is calculating a factorial of a number. Here's a typical implementation of this function:

Using Recursion:

int factorial (int num)
{
if (num==1)
return 1;
return factorial(num-1)*num; // recursive call
}
factorial() calls itself recursively, subtracting 1 from num on each call, until it equals 1.

Using Simple Looping Method:
As always, you can use iteration instead of recursion:
int factorial (int num)
{
int result=1;
for (int i=1; i<=num; ++i)
result=result*=i;
return result;
}

Append Element at the end of the Linked List...

void Append(NODE **head,int i) {

NODE *pTemp = *head;
NODE *newNode = (NODE *)malloc(sizeof(NODE));

newNode ->data = i;
newNode->next = NULL;
if(pTemp == NULL)
*head = newNode;
else {
while(pTemp->next != NULL)
pTemp = pTemp->next;
pTemp->next = newNode;
}
}

Insert element at head position into Linked List..

void AddAtHead (NODE **head, int i) {

NODE * newNode =(NODE *)malloc(sizeof(NODE));
newNode->data = i;
newNode->next = *head;
*head = newNode;
}

Removing Duplecate nodes from a linked list..

void RemoveDuplicates ( NODE**head) {
NODE *pTemp = *head;
if(pTemp ==NULL)
return;
else {
while(pTemp->next !=NULL) {
if(pTemp->data == pTemp->next->data) {
NODE *nnext = pTemp->next->next;
free(pTemp->next);
pTemp->next = nnext;
}
else
pTemp =pTemp->next;
}
}
}

How to build an expression trees ?

An expression tree is a binary tree which is built from simple operands and operators of an (arithmetic or logical ) expression by placing simple operands as the leaves of a binary tree and the operators as the interior nodes. If an operator is binary , then it has two nonempty subtrees, that are its left and right operands (either simple operands or sub expressions). If an operator is unary, then only one of its subtrees is nonempty, the one on the left or right according as the operator is written on the right or left of its operand. We traditionally write some unary operators to the left of their operands, such as "-" ( unary negation) or the standard functions like log( ), sin( ) etc. Others are written on the right, such as the factorial function ()!. If the operator is written on the left, then in the expression tree we take its left subtree as empty. If it appears on the right, then its right subtree will be empty. An example of an expression tree is shown below for the expression ( -a < b ) or ( c + d ) .

Explain Sparse Matrix...

A sparse matrix is one where most of its elements are zero. There is no precise definition as to know whether a matrix is sparsed or not, but it is a concept which we all can recognize intuitively. The natural method of representing matrices in memory as two-dimensional arrays may not be suitable for sparse matrices. That is one may save space by storing only those entries which may be nonzero. If this is done, then the matrix may be thought of as an ordered list of non-zero elements only. Information about a non-zero element has three parts:
an integer representing its row,
an integer representing its column and
the data associated with this element.
That is, each element of a matrix is uniquely characterized by its row and column position, say i, j. We might store that matrix as a list of 3-tuples of the form (i, j, data), as shown below,
Although the non-zero elements may be stored in the array in any order, keeping them ordered in some fashion may be advantageous for further processing. Note that above array is arranged in increasing order of the row number of non-zero elements. Moreover, for elements in the same row number, the array is arranged in order of increasing column number.

What is a priority queue?

As we know in a stack, the latest element is deleted and in a queue the oldest element is deleted. It may be required to delete an element with the highest priority in the given set of values and not only the oldest or the newest one. A data structure that supports efficient insertions of a new element and deletions of elements with the highest priority is known as priority queue. There are two types of priority queues: an ascending priority queue is a collection of items into which items can be inserted arbitrarily and from which only the smallest item can be removed. A descending order priority queue is similar but allows only the largest item to be deleted.

What is garbage collection?

Suppose some memory space becomes reusable because a node is released from a linked list. Hence, we want the space to be available for future use. One way to bring this about is to immediately reinsert the space into the free-storage list. However, this method may be too time-consuming for the operating system. The operating system may periodically collect all the deleted space onto the free-storage list. The technique that does this collection is called Garbage Collection. Garbage Collection usually takes place in two steps: First the Garbage Collector runs through all lists, tagging whose cells are currently in use, and then it runs through the memory, collecting all untagged space onto the free-storage list. The Garbage Collection may take place when there is only some minimum amount of space or no space at all left in the free-storage list, or when the CPU is idle and has time to do the collection. Generally speaking, the Garbage Collection is invisible to the programmer.

Explain Hashing..

Hashing or hash addressing is a searching technique. Usually, search of an element is carried out via a sequence of comparisons. Hashing differs from this as it is independent of the number of elements n in the collection of data. Here, the address or location of an element is obtained by computing some arithmetic function. Hashing is usually used in file management. The general idea is of using the key to determine the address of a record. For this, a function fun( ) is applied to each key, called the hash function. Some of the popular hash functions are: 'Division' method, 'Midsquare' method, and 'Folding' method. Two records cannot occupy the same position. Such a situation is called a hash collision or a hash clash. There are two basic methods of dealing with a hash clash. The first technique, called rehashing, involves using secondary hash function on the hash key of the item. The rehash function is applied successively until an empty position is found where the item can be inserted. If the hash position of the item is found to be occupied during a search, the rehash function is again used to locate the item. The second technique, called chaining, builds a linked list of all items whose keys hash to the same values. During search, this short linked list is traversed sequentially for the desired key. This technique involves adding an extra link field to each table position.

Explain AVL Trees.

For ideal searching in a binary search tree, the heights of the left and right sub-trees of any node should be equal. But, due to random insertions and deletions performed on a binary search tree, it often turns out to be far from ideal. A close approximation to an ideal binary search tree is achievable if it can be ensured that the difference between the heights of the left and the right sub trees of any node in the tree is at most one. A binary search tree in which the difference of heights of the right and left sub-trees of any node is less than or equal to one is known as an AVL tree. AVL tree is also called as Balanced Tree. The name "AVL Tree" is derived from the names of its inventors who are Adelson-Veilskii and Landi. A node in an AVL tree have a new field to store the "balance factor" of a node which denotes the difference of height between the left and the right sub-trees of the tree rooted at that node. And it can assume one of the
three possible values {-1,0,1}.

Explain Radix Sort.

This sorting technique is based on the values of the actual digits in the positional representations of the numbers being sorted. Using the decimal base, for example, where the radix is 10, the numbers can be partitioned into ten groups on the sorter. For example, to sort a collection of numbers where each number is a four-digit number, then, All the numbers are first sorted according to the the digit at unit's place.
In the second pass, the numbers are sorted according to the digit at tenth place. In the third pass, the numbers are sorted according to the digit at hundredth place. In the forth and last pass, the numbers are sorted according to the digit at thousandth place.
During each pass, each number is taken in the order in which it appears in partitions from unit's place onwards. When these actions have been performed for each digit, starting with the least significant and ending with most significant, the numbers are sorted. This sorting method is called the radix sort.
Let us take another example. Suppose we have a list of names. To sort these names using radix sort method we will have to classify them into 26 groups The list is first sorted on the first letter of each name, i.e. the names are arranged in 26 classes, where the first class consists of those names that begin with alphabet 'A', the second class consists of those names that begin with alphabet 'B' and so on. During the second pass each class is alphabetized according to the second letter of the name, and so on.

Explain Comparison Trees...

The comparison trees also called decision tree or search tree of an algorithm, is obtained by tracing through the actions of the algorithm, representing each comparison of keys by a vertex of the tree (which we draw as a circle). Inside the circle we put the index of the key against which we are comparing the target key. Branches (lines) drawn down from the circle represent the possible outcomes of the comparison and are labeled accordingly. When the algorithm terminates, we put either F (for failure) or the location where the target is found at the end of the appropriate branch, which we call a leaf, and draw as a square. Leaves are also sometimes called end vertices or external vertices of the tree. The remaining vertices are called the internal vertices of the tree. The comparison tree for sequential search is especially simple.

Explain Polish Notation.

The method of writing all operators either before their operation, or after them, is called Polish notation, in honor of its discoverer, the Polish mathematician Jan Lukasiewicz. When the operators are written before their operands, it is called the prefix form. When the operators come after their operands. It is called the postfix form, or, sometimes reverse Polish form or suffix form. In this context, it is customary to use the coined phrase infix form to denote the usual custom of writing binary operators between their operands. For example, the expression A + B becomes +AB in prefix form and AB+ in postfix form. In the expression A + B x C, the multiplication is done first, so we convert it first, obtaining first A + ( BCx ) and then ABCx+ in postfix form. The prefix form of this expression is +A x BC. The prefix and postfix forms are not related by taking mirror images or other such simple transformation. Also all parentheses have been omitted in the Polish forms.

If you are using C language to implement the heterogeneous linked list, what pointer type will you use?

The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type.

Inserting element into linked list

// Uses special case code for the head endvoid
SortedInsert(struct node** headRef, struct node* newNode) {
// Special case for the head end
if (*headRef == NULL && (*headRef)->data >= newNode->data) {
newNode->next = *headRef;
*headRef = newNode;
}
else {
// Locate the node before the point of insertionstruct
node* current = *headRef;
while (current->next!=NULL &&&& current->next->datadata) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;}}
}

// Dummy node strategy for the head endvoid
SortedInsert2(struct node** headRef, struct node* newNode) {
struct node dummy;struct node* current = &dummy;
dummy.next = *headRef;while (current->next!=NULL &&&& current->next->datadata) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
*headRef = dummy.next;
}

Reversing a linked list

void Reverse(struct node** headRef) {
struct node* result = NULL;
struct node* current = *headRef;
struct node* next;
while (current != NULL) {
next = current->next; // tricky: note the next node
current->next = result; // move the node onto the result
result = current;
current = next;
*headRef = result;
}
}