Archive

Posts Tagged ‘Recursion’

Find ‘ceil’ of a key in a Binary Search Tree (BST)

Long long time, eh?! But it has been a busy time at work. 🙂

So lets solve this problem. An example tree follows:

treeNow lets say you have the following queries –

q = 13, Answer = Does Not Exist

q = 5, Answer = 6

How do you go about finding the ceil?

One way to do it is Inorder Traversal of the tree. This will take O(n) time and then get you kicked out of the interview. Did you not read “BST” ? So we should be using that particular property of the tree!

Here is the algorithm you should be following in short

“Start with the root as current node.

If value(current node) == key, you are done!

If value(current node) > key, make answer = value(current node) and current node = leftNode(current node).

Else if value(current node)<key, make current node = rightNode(currentNode).

You have your answer once you exhaust nodes in the path you are moving on this fashion. If no value was assigned to answer, this indicates you kept moving right throughout and the tree has no value >= key.”

That does not sound right? Well, try it out for yourself! And the complexity? O(log n). Whoopie!

Advertisements
Categories: Recursion, Tree Tags: ,

Given a binary tree, find a branch whose elements sum up to a given number.

November 9, 2011 1 comment

Problem Statement: You have been given a binary tree with integer values. You are supposed to find if a branch exists  (ROOT node to LEAF node) such that the sum of all the values on this branch sums up to a given number ‘x’.

Let us work on the above binary tree. Assume x=26. Now the correct branch would be 2->7->6->11. So the answer is “Yes, such a branch exists”. I hope you understand the question now.

How would you go about solving this problem? If the first thought that came to your mind was “recursion”, kudos! That is in fact the correct way to solve this question. (And usually always the technique you use in questions involving trees)

This time we go for a top->bottom recursion and keep adding the sum everytime we move down in a branch. Now as soon as you reach the leaf, check your sum and return 1 (success) or 0 (failure) accordingly. Here is the algorithm:

int Check ( Node current, int sum ) //initial call with Check ( ROOT, 0)

{

sum = sum + current->VALUE

If ( current->LEFT != NULL)

int left = Check ( current->LEFT, sum )

If ( current-> LEFT !=NULL)

int right = Check ( current->RIGHT, sum )

If (current->LEFT == current->RIGHT == NULL )

{ //in case of LEAF nodes

If (sum==x)

return 1

Else

return 0

}

return (left || right) //return 1 IFF we receive SUCCESS (1) from any branch, left/right

}

Pretty simple to understand, right? So for the first time in the blog, we have applied recursion and used it while going it from top to bottom (if you get what I mean). 🙂

Cheerio!

PS: If you are wondering why we don’t return as soon as sum exceeds ‘x’, remember that the binary tree is said to have integers, which means negative numbers are allowed. 😉 Attention to detail!

Edit Distance between two strings (using Recursion)

October 31, 2011 1 comment

Problem Statement: Find the edit distance between two given strings. Edit distance is the minimum number of operations required to modify one string into the second one or vice versa. The operations allowed are as follows:

1. Delete a character

2. Replace a character with another one

3. Insert a character

For example,

String 1 = Hello

String 2 = Helo

The edit distance is 1 here, since we can convert 2 -> 1 by inserting an ‘l’.

Recursion is a Brute-Force method to solve this because it basically checks all the possibilities and finds the minimum number of operations. I am discussing this method as it is an exhaustive approach and gives you an idea of what edit distance is. So here is how the algorithms looks:

int EditDistance ( String1, String2, m, n )

{

If ( String2.length == n ) return (String1.length-m)

If ( String1.length == m) return (String2.length-n)

If ( String1[m] == String2[n] ) return EditDistance(String1, String2, m+1, n+1 )

If ( String1[m] != String2[n] )

   return 1+min(min(EditDistance(String1, String2, m, n+1), EditDistance(String1, String2, m+1, n)), EditDistance(String1, String2, m+1,n+1))

}

That is all! Let me explain it a little. What we are doing is moving forward through the strings until the end of any one is found. If the end is found (i.e., m/n match length) we return the length of the other string minus this string’s length as those many operations will be required from that point on. If the characters at the same position are same, then there is no problem. We move ahead. If they are not the same, then we check if the next character in the other array match this one (for detecting a required deletion/insertion).

There is a better approach, using Dynamic Programming for this problem. I’ll discuss it in the next post! 🙂

Implement Queue with a single Stack

October 24, 2011 5 comments

This is a very common problem that most of you might have even figured out. But I know a few who wouldn’t know how to do it. What would you have done if you could have used 2 stacks? You would have been manipulating the two, popping and pushing elements between the two to just make them work like a queue. Basically, you would have been using double the required space.

With 1 stack, the only way (as you might have figured out) is to use recursion. Once this concept comes to mind, things become sweet and simple. For Enqueuing, you just need to PUSH an element onto the stack. So that is no hassle. For Dequeuing, what you need to do is recurse to the bottom of the stack by POP-ing elements (which is somewhat similar to how we used to tackle tree-related problems with recursion) and then print the last element. You again PUSH the rest of the elements on to the stack while coming bottom->up. 

Here is a pseudo code for both the functions :

void ENQUEUE ( element )

{

stacky_queue.PUSH (element) //stacky_queue is basically my stack

}

bool DEQUE ()

{

If ( NOT stacky_queue.EMPTY())

{

popped_element = stacky_queue.POP()

IF ( NOT DEQUE() )

{

PRINT popped_element

}

ELSE

{

stacky_queue.PUSH(popped_element)

}

return true

}

return false

}

Cool, eh? Hope you got it! If not read the paragraph in italics once more and you certainly will understand it then! 🙂

Reverse a stack without using any other data structures. (in-place)

This was a question that was asked to one of my friends in Microsoft’s IDC interview. No other data structures, eh? And I am pretty sure that  I would need all the values to reverse the stack. So there is only one way to this. Solve the problem using recursion!

But how? How do you utilize recursion to do this? Here is how you should proceed. Recurse down to the second last element in the stack and call a function with the stack as it is right now (with only 1 element) and the current element (the second last one). Now go on to pop an element. Then you should do one of the two things. If the size is not equal to zero, call this function again with the element you received from the function (2nd last). If the size is zero, just push the element you received from the call onto the stack.

So you are basically inserting each element in reverse order utilizing 2 functions. Here is a small pseudo-code:

void reverse(Stack s) //called at the start
{
int num = (int)s.Pop();
if (s.Count != 1)
reverse(s);
Push(s , num);
}
void Push(Stack s , int a)
{
int num = (int)s.Pop();
if (s.Count != 0)
Push(s , a);
else
s.Push(a);
s.Push(num);
}

You got it, right? If not, try running this for a basic input stack with values 1,2,3,4,5 (bottom -> top). You’ll certainly get it then. 🙂

Find the diameter of a tree.

First things first, what is the diameter of a tree? It is the maximum possible distance between any two nodes in a given tree. The nodes can or cannot be leaf nodes. Now that we know what the question means, let us start thinking about how we should approach this problem.

It should be inherently clear to you that recursion is the best way to go about this. So what kind of recursion-traversal should I adopt? A top-down one? Or a bottom-up one? You have previously seen examples of the bottom-up approach using recursion while finding depth of trees, etc. We can use the very same approach here as well.

Traverse down to the leaf nodes. Now move up one by one returning 1 from the leaf nodes. The value you should return from any node that is not a leaf node is the one that is greater (when comparing the one you get from the left and right branches) + 1. Also, at each node, compare the addition of the two values that you get from your left and right branches to a global variable that stores the maximum diameter of the tree that has been reached till now while going bottom->up. When you reach the root and then the first call of your function, the value returned is not important (and is not necessarily the diameter). The global variable has the diameter of the tree. 😉

An easy pseudo-code for this can be written as,

int tree_diameter=0;

int diameter ( node * curr ) //curr is ROOT for the first call

{

if ( curr->left NOT equal to NULL)

{

int l = diameter( curr->left );

}

if (curr->right NOT equal to NULL)

{

int r = diameter( curr->right );

}

if ( curr->left EQUAL to NULL and curr->right EQUAL to NULL)

{

return 2; //for leaf node 

}

if ( l+r-1 > tree_diameter ) //checking if max length at this point is greater than currently stored diameter

{

tree_diameter=l+r-1;

}

if ( l>r )

return l+1;

else

return r+1;

}

You will finally get the diameter of your tree in the variable tree_diameter . Of course, it need not be a global variable and other ways can be used as an alternative to making the variable global. But that isn’t really what we are discussing in this post. You got the pseudo-code, right? Go to the bottom, start going up, at each point calculate current maximum length till you reach ROOT. Bomb! 🙂

Find the lowest common ancestor of two given nodes in a tree.

This question was pretty much a favorite at my Microsoft interviews. Interviews were asking this one left and right. The only bit of tricky part is that you cannot assume that the tree has back-pointers. Take  a binary tree with pointers pointing from parent to children. That is it.

So what do you think is the best way to do this? I mentioned in the post where we found the depth of the tree using recursion that it is the best way to deal with trees which aren’t too huge. This is the very same. You can once again recurse to the leaf nodes. Then start moving up and return 1 when you find one of the two given nodes or when the value you are receiving from the left or right side is 1. Here, 1 indicates that one of the nodes has been found somewhere beneath that point. So the node where you get a 1 from both left and right sides, is the node you want!

Hope you got that logic. If not, here is a pseudo-code. Perform a dry run for any tree and see how things work out :

int ancestor (node * curr,  node * node1, node * node2) //curr will be root for the first time

{

if(node1==node2)

{

PRINT “BOTH NODES SAME”;

}

if (curr->left NOT equal to NULL)

{

int l = ancestor (curr->left, node1, node2);

}

if (curr->right NOT equal to NULL)

{

int r = ancestor (curr->right, node1, node2);

}

if(curr-> right EQUAL to NULL and curr->left EQUAL to NULL)

{//leaf node

if(curr == node1 or curr=node2)

return 1;

else

return 0;

}

if (l+r ==2)

{

PRINT “YOU FOUND YOUR NODE”;

//do the needful

}

if(curr == node1 OR curr=node2)

{

return l+r+1;

}

return l+r;

}

Now that was a simple code. If you didn’t get anything, the comments are always open.

%d bloggers like this: