Circular Doubly Link List from the binary tree

Write code for converting a tree in to Doubly Linked List using existing nodes only in single traversal.

Logic:
Do the inorder traversal of the list and update the pointers keeping track of the last visited node.

createDLL( struct node * root, struct node ** last_node, struct node ** head)
{
if(root == NULL) return;
if(root->left == NULL and root->right == NULL && *head == NULL)
{
*last_node = root;
*head = root;
return;
}

createDLL(root->left);
if(*last_node = NULL)
{
*head = root;
*last_node = root;
return;
}
(*last_node)->right = root;
root->left = *last_node;
*last_node = root;
createDLL(root->right);
}

// head points to the final doubly link list
In main make the last node right point to the head
and head left point to last node.

First Unrepeated character in a string.

Question: Given a string,find the first un-repeated character in it.

SOlution 1:
In case the string is a valid string. It has only characters a to z then we can create an array of size 26. Initialize each element in the array to 0 and then once u find a character go to that index and increment the value of array[character - 'a']

Scan again the original array and check the value of array[index-'a'] if the value is not set then it is the first un-repeated character.

Missing One

Given an array of size n. It contains numbers in the range 1 to n. Only one number is missing.Find the numbers which aren’t present.

Solution 1:

FInd the sum of all the numbers in the array
Find the sum of numbers using the formulae n(n+1)/2

Do the difference sum2 - sum1. Difference is the missing number.

Solution 2:
The problem in the above solution is that the over flow might happen since we are doing the sum of so many numbers.
Over flow can be taken care by forming a link list to store the numbers. 65535 is the maximum value of a 16 bit integer. So when the sum value reaches 65535 make a new node and append it at the starting of the list.keep the value of the sum- 65535 in new node. And keep on inserting nodes till the value is less 65,535.



Other solution could be we can xor the numbers in the array with the number 1 to n.

value = a[0]
for(int i = 1; i less than n; i++)
value = value xor array[i];

for(int i =1;il ess than n+1 ;i++)
value = value xor i;

value will have the answer finally. Since xor with same numbers will cancel out..

Two Numbers Missing in an array

Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.
Example: Size = 5 { 1,2 3 }

Logic We can find the two numbers as follows.

Do the sum of all the numbers in the array call it sum1
Find the sum of numbers using the formulae ((n) (n+1))/2 sum2

Do the sum of squares of all the numbers in the array call it sum3
Find the sum of all squares of n numbers using the formulae (n(n+1) (2n+1))/6 = sum4

x + y = sum2 - sum1
x^2 + y^2 = sum4 - sum3

Solve these two equations You will get the answer.

Kth Element in the Binary Search Tree

Given a Binary Search Tree, write a program to print the kth smallest element without using any static/global variable. You cant pass the value k to any function also.

Solution: In case you are allowed to use the extra space, and there is no condition you just have to specify the kth element in the binary search tree. You can simply do inorder and keep a counter, when the counter becomes equal to k print the element

The code for that would be:

KthElement(struct node * root, int count, int k)
{
if( root)
{
KthElement(root->left, count,k);
count ++;
if( count == k)
return root->data;
KthElement(root->right,count,k);
}
}

to follow the condition of the above question, we dont have to pass the value of the variable to it and we cant keep any global variable. We can do it by doing the inorder in an iterative manner. Logic would be.
Use a stack. Traverse till the left and while traversing push the nodes in the stack.
Pop each node from the stack and then traverse to its right and again iteratively follow the same procedure of going to left and so on.

The code would look like this:

KthElementIterative(struct node * root, int k)
{
struct node * temp = root;
struct node * x;

push(root);
temp = temp->left;

while( stack is not empty)
{

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

x = pop();
count ++;

if(count == k )
break;


if( x->right)
{push(x-right);temp = x->right;}

else temp=null;

}

return x->data;
}

Bracket Printing

You are given an integer. You have to print the valid paranthesis set corresponding to the number n.
Example: Number n = 2 Valid paranthesis set is ( ) ( ) ( ( ) )
Number n = 3 Valid paranthesis set is ( ) ( ) ( ) ( ( ) ( ) ) ( ( ( ) ) )

Logic:

Represent the bracket pairs as a combination of 1 and 0. Like ( ) is 1 0, ( ( ) ) is 1 1 0 0, ( ( ( ) ) ) is 1 1 1 0 0 0
When you get n as the input create a tree having the right child as 1 and left child as 0
for n = 2 structure of the tree would be

-----------------(1)
----------------/ \
---------------/-- \
--------------(0) (1)
--------------\---- /
---------------\ --/
--------------(1) (0)
---------------/-- /
--------------/ --/
------------(0) -(0)

Printing the brackets: Traverse if u find the value as 1 put the character ( in the array else put the character ) in the array.
WHen the length of the array becomes equal to the number given as input. You are done print the array.

Pseudo Code to create the tree:

createTree(struct node * null, int n, int OneCount, int ZeroCount)
{
if(root == Null)
{
root = makenode(1);
OneCount++;
}

if( ZeroCount <>left = makenode(0);
createTree(root->left,n,OneCount,ZeroCount);
}

if(OneCount <>right = makenode(1);
createTree(root->right,n,OneCount,ZeroCount);
}
}

PseudoCode To Read the Tree:

First Call will be made to this fucntion like PrintBrackets( root, n, array, 0);


PrintBrackets(struct node *root, int n, int * array, int index)
{

if(root == null)
return;

if(root->data == 1)
array[index]= '(';

if(root->data == 0)
array[index] = ")';

if(index == n-1)
puts(array);
return;

if(root->left)
PrintBrackets(root->left, n,array,index+1)

if(root->right)
PrintBrackets(root->right, n,array,index+1)

}

Least Common Parent of two nodes in a Binary Search Tree

Write the code to find out the least common ancestor of two nodes (a and b) in a binary search tree. Complexity o(logn)

Logic:
Since it is a binary search tree. We can check at every node whether the values of a and b lie to the left or right. In case they lie to the left, we can move to the left recursively. else we can move to the right recursively. When u get a node such that the value of node lies between a and b return.

// check always send the a node as the one which has a lower value as compared to the node b value

struct node * leastCommonAncestor(struct node * root, struct node * a, struct node * b)
{
if( root == NULL)
return NULL;

if( a->data <= root->data && b->data > root->data)
return (root);

else if( a->data <>data && b->data <>data)
return(leastCommonAncestor(node->left, a, b));

else if( a->data > root->data && b->data > root->data)
return(leastCommonAncestor(node->right, a, b));

}

Data Structure : Insert , Delete, Update

Design a data structure that does all these operations optimally
1. Insert
2. Delete
3. Search

COnsider the intput as a set of integers. The data structure that could be used is :

struct node
{
int data;
struct node * next;
}

Now we can have an array of the pointers to nodes

struct node * array[10]; // Mapped from 0 to 9

void Insert (int x)
{
y = hash(x); // hash will reurn the number between 0 to 9
struct node * temp;
temp = createnode(x);
temp-> next = array[y]->next;
array[y]->next = temp;
}

The complexity of the insert operation is o(1)

void delete(int x)
{
y = hash(x);
struct node * temp;
temp = array[y]->next;
prev = array[y];
while(temp!= NULL)
{

if(temp->data == x)
{
prev-next = temp->next;
}
prev = temp;
temp = temp->next;
}

The complexity of the delete operation would be, worst case is when the element is at the end of the list pointed by any array index. So the worst case would be o(length of the link list)

void search(int x)
{
y = hash(x);
loop to get the value of the node.
}

The complexity will be same as the delete.