How to delete a node in the singly link list ?

Given a pointer to a node in a singly linked list, how do you delete the node ?
A simple solution is to traverse the linked list until you find the node you want to delete. But this solution requires pointer to the head node which contradicts the problem statement.
Fast solution is to copy the data from the next node to the node to be deleted and delete the next node. Something like following.

    struct node *temp  = node_ptr->next;
   node_ptr->data  = temp->data;
   node_ptr->next  = temp->next;
   free(temp);

In java, the code would look something like this :

1	public void deleteNode(Node node){

2	Node temp = node.next;

3	node.data = temp.data;

4	node.next = temp.next;

5	//do nothing with temp and let the garbage collector remove it

6

}

Continue

Vertical sum of binary tree

Find vertical sum of given binary tree.

Example:

Code:

     1
   / \
 2     3
/ \   / \
4   5 6   7

The tree has 5 vertical lines
Vertical-1: nodes-4 => vertical sum is 4
Vertical-2: nodes-2 => vertical sum is 2
Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12
Vertical-4: nodes-3 => vertical sum is 3
Vertical-5: nodes-7 => vertical sum is 7
We need to output: 4 2 12 3 7

We can do an inorder traversal and hash the column. We call Traverse(root, 0) which means the root is at column 0. As we are doing our traversal, we can hash the column and increase its value by T.data. A rough sketch of my function looks like this -

Traverse(Tree T, int column)
{
if(T==NULL) return;
Traverse(T.left, column-1);
Hash(column) += T.data;
Traverse(T.right, column+1);
}

Traverse(root, 0);
Print Hash

Continue

How to Rebuild a binary tree from Inorder and Preorder traversals ?

This is a well known problem where given any two traversals of a tree such as inorder & preorder or inorder & postorder or inorder & levelorder traversals we need to rebuild the tree.

The following procedure demonstrates on how to rebuild tree from given inorder and preorder traversals of a binary tree:

• Preorder traversal visits Node, left subtree, right subtree recursively
• Inorder traversal visits left subtree, node, right subtree recursively
• Since we know that the first node in Preorder is its root, we can easily locate the root node in the inorder traversal and hence we can obtain left subtree and right subtree from the inorder traversal recursively

Consider the following example:

Preorder Traversal: 1 2 4 8 9 10 11 5 3 6 7

Inorder Traversal: 8 4 10 9 11 2 5 1 6 3 7

Iteration 1:

Root – {1}

Left Subtree – {8,4,10,9,11,2,5}

Right Subtree – {6,3,7}

Iteration 2:

Root – {2} Left Subtree – {8,4,10,9,11} Right Subtree – {5}

Root – {3} Left Subtree – {6} Right Subtree – {7}

Iteration 3:

Root – {2} Left Subtree – {8,4,10,9,11} Right Subtree – {5}		Root – {3} Left Subtree – {6} Right Subtree – {7}
Root – {4} Left Subtree – {8} Right Subtree – {10,9,11}	Done	Done

Iteration 4:

Root – {2} Left Subtree – {8,4,10,9,11} Right Subtree – {5}			Root – {3} Left Subtree – {6} Right Subtree – {7}
Root – {4} Left Subtree – {8} Right Subtree – {10,9,11}		Done	Done
Done	R – {9} Left ST – {10} Right ST-{11}	Done	Done

The following are the two versions of programming solutions even though both are based on above mentioned algorithm:

• Creating left preorder, left inorder, right preorder, right inorder lists at every iteration to construct tree.
• Passing index of preorder and inorder traversals and using the same input list to construct tree.

Continue

O(1) stack operations.

Design a datastructure to implement a stack such that ALL of push(), pop() and getMax() functions work in O(1) time. You have infinite memory at your disposal.
Also note that function getMax() just returns the element with maximum value in the stack and NOT delete it from the stack like what pop() does.

Insight : compress the information using diff

PUSH :
if stack empty
push(elem)
push(elem)
else
min = pop()
push(elem-min)
push(min)

POP :
min = pop()
elem = pop()
if elem is -ve
   push(min-elem) // earlier min  
    return min
else
   push(min)
    return elem + min 

MIN :
min = pop()
push(min)
return min 

O(n+1) space and  constant operations for pop push min !! 

Continue

What is the difference between the stack and the heap? Where are the different types of variables of a program stored in memory?

When a program is loaded into memory, it is organized into three areas of memory, called segments: the text segment, stack segment, and the heap segment. The text segment (sometimes also called the code segment) is where the compiled code of the program itself resides. This is the machine language representation of the program steps to be carried out, including all functions making up the program, both user defined and system.

The remaining two areas of system memory is where storage may be allocated by the compiler for data storage. The stack is where memory is allocated for automatic variables within functions. A stack is a Last In First Out (LIFO) storage device where new storage is allocated and deallocated at only one "end", called the Top of the stack. When a program begins executing in the function main(), space is allocated on the stack for all variables declared within main(). If main() calls a function, func(), additional storage is allocated for the variables in func() at the top of the stack. Notice that the parameters passed by main() to func() are also stored on the stack. If func() were to call any additional functions, storage would be allocated at the new Top of stack. When func() returns, storage for its local variables is deallocated, and the Top of the stack returns to its old position. If main() were to call another function, storage would be allocated for that function at the Top. The memory allocated in the stack area is used and reused during program execution. It should be clear that memory allocated in this area will contain garbage values left over from previous usage.

The heap segment provides more stable storage of data for a program; memory allocated in the heap remains in existence for the duration of a program. Therefore, global variables (storage class external), and static variables are allocated on the heap. The memory allocated in the heap area, if initialized to zero at program start, remains zero until the program makes use of it. Thus, the heap area need not contain garbage.

Continue

Can we do a Binary search on a linked list?

Great C datastructure question!

The answer is ofcourse, you can write a C program to do this. But, the question is, do you really think it will be as efficient as a C program which does a binary search on an array?

Think hard, real hard.

Do you know what exactly makes the binary search on an array so fast and efficient? Its the ability to access any element in the array in constant time. This is what makes it so fast. You can get to the middle of the array just by saying array[middle]!. Now, can you do the same with a linked list? The answer is No. You will have to write your own, possibly inefficient algorithm to get the value of the middle node of a linked list. In a linked list, you loosse the ability to get the value of any node in a constant time.

One solution to the inefficiency of getting the middle of the linked list during a binary search is to have the first node contain one additional pointer that points to the node in the middle. Decide at the first node if you need to check the first or the second half of the linked list. Continue doing that with each half-list.

Continue

What is an AVL tree?

AVL trees are self-adjusting, height-balanced binary search trees and are named after the inventors: Adelson-Velskii and Landis. A balanced binary search tree has O(log n) height and hence O(log n) worst case search and insertion times. However, ordinary binary search trees have a bad worst case. When sorted data is inserted, the binary search tree is very unbalanced, essentially more of a linear list, with O(n) height and thus O(n) worst case insertion and lookup times. AVL trees overcome this problem.

An AVL tree is a binary search tree in which every node is height balanced, that is, the difference in the heights of its two subtrees is at most 1. The balance factor of a node is the height of its right subtree minus the height of its left subtree (right minus left!). An equivalent definition, then, for an AVL tree is that it is a binary search tree in which each node has a balance factor of -1, 0, or +1. Note that a balance factor of -1 means that the subtree is left-heavy, and a balance factor of +1 means that the subtree is right-heavy. Each node is associated with a Balancing factor.


Balance factor of each node = height of right subtree at that node - height of left subtree at that node.



Please be aware that we are talking about the height of the subtrees and not the weigths of the subtrees. This is a very important point. We are talking about the height!.


Here is some recursive, working! C code that sets the Balance factor for all nodes starting from the root....


#include

typedef struct node
{
int value;
int visited;
int bf;
struct node *right;
struct node *left;
}mynode;

mynode *root;

mynode *add_node(int value);
void levelOrderTraversal(mynode *root);
int setbf(mynode *p);


// The main function
int main(int argc, char* argv[])
{
root = NULL;

// Construct the tree..
add_node(5);
add_node(1);
add_node(-20);
add_node(100);
add_node(23);
add_node(67);
add_node(13);

// Set the balance factors
setbf(root);

printf("\n\n\nLEVEL ORDER TRAVERSAL\n\n");
levelOrderTraversal(root);
getch();
}

// Function to add a new node to the tree...
mynode *add_node(int value)
{
mynode *prev, *cur, *temp;

temp = (mynode *) malloc(sizeof(mynode));
temp->value = value;
temp->visited = 0;
temp->bf = 0;
temp->right = NULL;
temp->left = NULL;

if(root==NULL)
{
//printf("\nCreating the root..\n");
root = temp;
return;
}

prev=NULL;
cur=root;

while(cur!=NULL)
{
prev=cur;
cur=(valuevalue)?cur->left:cur->right;
}

if(value <>value)
prev->left=temp;
else
prev->right=temp;

return(temp);

}


// Recursive function to set the balancing factor
// of each node starting from the root!
int setbf(mynode *p)
{
int templ, tempr;
int count;
count = 1;

if(p == NULL)
{
return(0);
}
else
{
templ = setbf(p->left);
tempr = setbf(p->right);

if(templ < tempr)
count = count + tempr;
else
count = count + templ;
}

// Set the nodes balancing factor.
printf("\nNode = [%3d], Left sub-tree height = [%1d], Right sub-tree height = [%1d], BF = [%1d]\n",
p->value, templ, tempr, (tempr - templ));
p->bf = tempr - templ;
return(count);
}



// Level order traversal..
void levelOrderTraversal(mynode *root)
{
mynode *queue[100] = {(mynode *)0};
int size = 0;
int queue_pointer = 0;

while(root)
{
printf("\n[%3d] (BF : %3d) ", root->value, root->bf);

if(root->left)
{
queue[size++] = root->left;
}

if(root->right)
{
queue[size++] = root->right;
}

root = queue[queue_pointer++];
}
}


And here is the output...


Node = [-20], Left sub-tree height = [0], Right sub-tree height = [0], BF = [0]
Node = [ 1], Left sub-tree height = [1], Right sub-tree height = [0], BF = [-1]
Node = [ 13], Left sub-tree height = [0], Right sub-tree height = [0], BF = [0]
Node = [ 67], Left sub-tree height = [0], Right sub-tree height = [0], BF = [0]
Node = [ 23], Left sub-tree height = [1], Right sub-tree height = [1], BF = [0]
Node = [100], Left sub-tree height = [2], Right sub-tree height = [0], BF = [-2]
Node = [ 5], Left sub-tree height = [2], Right sub-tree height = [3], BF = [1]


LEVEL ORDER TRAVERSAL

[ 5] (BF : 1)
[ 1] (BF : -1)
[100] (BF : -2)
[-20] (BF : 0)
[ 23] (BF : 0)
[ 13] (BF : 0)
[ 67] (BF : 0)




Here is the tree which we were dealing with above


5
1 100
-20 23
13 67




After insertion, the tree might have to be readjusted as needed in order to maintain it as an AVL tree. A node with balance factor -2 or 2 is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees, possibly stored at nodes. If, due to an instertion or deletion, the tree becomes unbalanced, a corresponding left rotation or a right rotation is performed on that tree at a particular node. A balance factor > 1 requires a left rotation (i.e. the right subtree is heavier than the left subtree) and a balance factor < -1 requires a right rotation (i.e. the left subtree is heavier than the right subtree).


Here is some pseudo code to demonstrate the two types of rotations...


Left rotation


BEFORE

0 (par)

0 0 (p)

0 0 (tmp)

0 0 0 0
(a) (b)



Here we left rotate the tree around node p



tmp = p->right;
p->right = tmp->left;
tmp->left = p;

if(par)
{
if(p is the left child of par)
{
par->left=tmp;
}
else
{
par->right=tmp;
}
}
else
{
root=tmp;
}

// Reclaculate the balance factors
setbf(root);




AFTER
0 (par)

0 0
(tmp)

0 0
(p) (b)

0 0
(a)

0 0






Right rotation


BEFORE

0 (par)

0 0 (p)

0 (tmp) 0

0 0 0 0
(a) (b)



Here we right rotate the tree around node p


tmp = p->left;
p->left = tmp->right;
tmp->right = p;

if(par)
{
if(p is the left child of par)
{
par->left=tmp;
}
else
{
par->right=tmp;
}
}
else
{
root=tmp;
}

// Recalculate the balancing factors...
setbf(root);




AFTER

0 (par)

0 0 (tmp)

0 0
(a) (p)

0 0
(b)

0 0




**

Continue