Archive

Archive for the ‘Tree’ Category

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!

Categories: Recursion, Tree Tags: ,

Boggle Solver

A facebook recruiter asked me to write the code for this particular problem. While I was able to suggest the algorithm correctly, I messed up my code. So here is the problem statement:

Given a 4×4 array with randomly selected letters in it and a dictionary of valid words, find which words can be made from this array by starting from any of the 16 letters and moving in any direction (the only constraint being that you cannot come to a node twice while making a word)

The first thing you should see here that this is clearly a Graph problem. The second noticeable aspect is that the maximum length of a word from such an array (with the constraint) can be 16 and the minimum length can be 1.

Since you have to look for all possible combinations starting from every point, Depth First Search comes to mind (why not Breadth First Search? Think about it). What you should do is apply DFS starting at each of the 16 nodes in the array. At every step, you add the newly formed word to a data structure meant to store strings (not allowing duplicates).

Once you have this data structure ready with you, all you need to do is search for each word in the dictionary that you have been provided. 🙂

Clear enough?

PS: Please code the DFS in the 4×4 array. It is not as simple as you assume it to be. 🙂

PPS: Does anyone have a better solution?

Tries (Overview)

January 27, 2012 1 comment

What is it? Trie? Did you mean “Tree”? No! I meant “Trie”. It is a data structure (also known as “prefix tree”) that is used in form of a dictionary. It is basically a way of representing data. I don’t think I can explain this without an example. So here we see the way to represent two words in English language using a trie. Shrey and Shayne.

As you can see, a trie gives us words with the same prefixes. In this example, “SH”. So that is how you represent words. You can do the same for numbers (in any format – binary, decimal, etc). Also, note that both have different “Y” nodes because a trie represents words on the base of prefixes. If we associate a count with each node, we can also tell the number of words starting with a particular prefix.

Please note that the insertion in a trie takes O(length) time where length is that of the word being inserted. We can create a trie for english language using a structure with information and 26 pointers for the corresponding letters. Easy, eh?

So a trie can be of many uses. In the next post, we’ll see an example of using Trie. 🙂

PS : For more information on Tries, visit http://en.wikipedia.org/wiki/Trie

PPS : Sorry for the long hiatus in posting!

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!

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.

Find the depth of a tree without using recursion

In my last post, I discussed how to find  the depth of a tree using recursion. Now I’ll point out the way of doing this without using recursion. I hope everyone knows what a Breadth-First Search (BFS) is. To explain it in short, you add all the child nodes of root in a queue. Then you pop a node out of the front and add the child nodes of that to the end of the queue. In this way, you traverse a tree in a  Breadth-First manner.

Similarly, all you need to do is add a random value “X” to the queue once you have added the children of root. Now start popping and proceed with BFS. When you encounter the “X”, you add another “X” at the end of the queue and increase the value of depth (initially 0). In essence, every “X” occurs after you have added the nodes at one level. So your depth variable ends up having the number of “X”es or depth of the tree at the end of your program when your queue is empty. 🙂

Here is the algorithm (in words) to make things clearer,

1. Add ROOT to queue

2. Pop ROOT, Add its child nodes to queue, Add “X” to queue

3. Pop elements from queue. (If not “X”, add its child nodes to the queue, else, add “X” to the queue and increment depth)

4. Go to Step 3 till queue is NOT empty.

You have it! The depth of your tree in time complexity O(V+E). This method is useful when you don’t have a lot of memory to use and can’t afford to load the memory stack through recursion.

See you soon!

%d bloggers like this: