Check Whether a tree is a binary Search Tree or not

Iterate over the Binary Search Tree. Keep track of the last node traversed. If you find at any point the prev node > the current node under examination return false



prev_data = -infinity initially

boolean checkBST(node)
{
if(node == null) return true;
if(checkBST(node->left) == false) return false;
if(prev_data > node->data)
{
return false;
}else
{
prev_data = node->data
}
if(checkBST(node->right) == false) return false;
return true;
}

Circular Doubly Link List out of a Binary Search Tree

The function convert converts the given binary search tree into a circular doubly link list and gives the pointer of the first node.

node convert(root)
{
if(root == null) return null;

else if(root.left == null && root.right == null)
{
root.left = root;
root.right = root;
return root;
}
else if(root.left == null && root.right != null)
{
rightnode = convert(root.right);
root.left = rightnode.left;
rightnode.left.right = root;
return root;
}
else if(root.right== null && root.left!= null)
{
leftnode = convert(root.left);
leftnode.left.right = root;
root.left = leftnode.left;
return leftnode;
}
else
{
leftnode = convert(root.left);
leftnode.left.right = root;
root.left = leftnode.left;
rightnode = convert(root.right);
rightnode.left.right = leftnode;
leftnode.left = rightnode.left;
rightnode.left = root;
root.right = rightnode;
}
}

Good Resources

http://www.codechef.com/problems/

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.