AlaaShaker's Weblog

// untitled …

Link-the-Tree SOLVED [Problem of the Week]

with 2 comments

This week’s problem was was pretty easy – obviously for ACMers only!!

Anyway, here’s the solution. You were given a binary tree, not necessarily complete (most people overlooked this point, and hence they didn’t handle having nodes with only left or only right nodes – they just assumed that every node either has both or not!). The task was transforming that tree into a linked list by adding a Next pointer to the struct. Here’s a diagram that would make explaining such story much easier (my diagram, that’s why it sure looks better .. LOL):

linkthetreesolved1

On the left, you’ll find the original binary tree, along with two pointers, R and C, that I’ll use to solve the problem as you’ll see in a moment. On the right, this is the required output.

Now, the solutions is pretty straight forward. Think of R and C as two pointers that follow each other. C is the fast pointer that performs the linking process, while R plays as the slow pointer that points to the Node you navigate from to left or right child nodes.

Initially, both R and C are set to point at the root node, node A. We’ll keep R as it is, and move C around to do our linking. If R (node A) has a left node, then Next should point to node B (by setting C->Next = R->Left) then moving C there (C = C->Next). If R (node A) has a right node, do the same, and having C eventually at node C. If we moved R earlier, we couldn’t have navigated or direct C around. Now, since we’re done, we can move R forward (R = R->Next) and by that it now points to node B (and C still points to node C).

Similarly, we can also direct and move pointer C around from node C to node D then to node E, since pointer R still points to node B. Then, R moves to node C (as we said, R = R->Next) and C will link nodes F then G in the same fashion. If you follow the code, you will find that it also handles special cases as in node E (with only one left and no right) and node F (with only one right and no left). The code runs in an infinite loop, till the pointers R and C meet (at node I) when it breaks. This way, the code runs in a linear fashion, not recursively.

Here’s the function that does that: (C++)

void TreeToLinked(Node* root)
{
// Both pointers initially point to the root node ...
Node* R = root;
Node* C = root;

while(true)
{
if(R->Left) // Left check
{
C->Next = R->Left;
C = C->Next; // Link and move forward ...
}
if(R->Right) // Right check
{
C->Next = R->Right;
C = C->Next; // Link and move forward ...
}

R = R->Next; // Move the slow, anchor pointer forward now ...

// Check if both pointers meet.
// If yes, break the loop and exit ...
if(R == C)
break;
}
}

A common mistake is that many people do the left check else if the right check. They should be checked separately.

If the previous function is correct, the following function should succeed in printing the correct output:

void DisplayLinkedList(Node *root)
{
while(root->Next)
{
cout<<root->ch<<&quot; > &quot;;
root = root->Next;
}
}

The output should be:

A > B > C > D > E > F > G > H > I

This week’s winners:

  • Hatem Abdel Ghani
  • Mohamed Samy
  • Metal
  • Mahmoud Osama

Thanks to everyone who gave it a shot. Congrats to the winners, keep it up 😉

Thanks to Roaa, who solved it 90% at the time she was very sick …

Correct solutions are now approved on the original post for those who want to check it. See you next week isA …

Advertisements

Written by AlaaShaker

August 28, 2008 at 9:15 pm

Posted in Problems

Tagged with , , ,

2 Responses

Subscribe to comments with RSS.

  1. […] Click here to see the solution and the winners’ list … […]

  2. Keep it comin’ Alaa :] Hope the next problem will be harder and as interesting as this one!

    P.S. I’m not an ACMer, not yet anyway..

    Metal_

    August 29, 2008 at 12:32 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: