AlaaShaker's Weblog

// untitled …

Link-the-Tree [Problem of the Week]

with 35 comments

Seems that last week’s problem was a bit difficult as Fouad stated in his last problem, so this weeks it’s an easier one .. not that easy though. It should be easy for all ACMers .. we’ll see!
I first met this problem in a physical Microsoft technical interview (and solved it a7l), which stresses how being an ACMer helped me a lot in passing interviews. Actually, that Microsoft interview is broken into four interviews: three in problem solving (= ACM) and one in System Architecture, Analysis and Design.

Anyway, here’s how this problem goes ..

Incomplete Binary Tree

You have a binary tree, not necessarily complete, where each Node holds two pointers (left and right) and a character as an identifier. Here’s the structure of the Node:

   1: struct Node
   2: {
   3:     char ch;
   4:     Node *Left;
   5:     Node *Right;
   6: }

Your task is to create some linear function, that transforms that binary tree into a linked list, following a row-by-row fashion. You are asked to add in each Node an additional pointer, Next, that points to the next Node in the linked list. Inside your function, you’re allowed to create pointers as much as you need. But, do not use any other data structures to solve the problem (i.e. do not solve it using a queue for instance), just the additional pointer and your processing. Do not create a new linked list, just edit the existing tree as it is. You can assume Next is set to NULL, initially – so, just assign the correct values to each one of them!
Write the function that does that ..

So, as an example, check the figure above. The resulting linked list should contain:

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

Again, in a row-by-row fashion:

[ (level 0 : ) A >
  (level 1 : ) B > C >
  (level 2 : ) D > E > F > G >
  (level 3 : ) H > I ]

I will require code, and I mean by that code that compiles! πŸ˜€
Results by Friday isA, or when I get five correct results, the earlier ..
And as usual, only wrong solutions will be posted till then.

Solution Posted

Click here to see the solution and the winners’ list …

Advertisements

Written by AlaaShaker

August 24, 2008 at 4:08 pm

35 Responses

Subscribe to comments with RSS.

  1. To TeCNoYoTTa:
    I did not get a word of what you wrote. So, I kindly ask you to send me clear code that actually compiles … please πŸ˜€
    Worst cases, write pseudo code .. but English code, NO, doesn’t work πŸ˜€

    AlaaShaker

    August 24, 2008 at 7:05 pm

  2. use a queue

    anonymous

    August 24, 2008 at 9:01 pm

  3. Alaa, how are you man? It seems I missed your first problem!

    Anyway I see this one is about level-order traversal. So let’s warm up πŸ™‚

    I assume that all the “Next” pointers are set to NULL at the beginning. I also assume that whenever a node has no child at one of its branches, whether the left, the right or both, then this branch is set to NULL too. The parameter “tree” expects a pointer to the root node of the tree.

    void TreeToList ( Node* tree )
    {
    Node *cur, *last;
    cur = last = tree;
    while(cur!=NULL)
    {
    if ( last->next = cur->left )
    last = last->next;
    if ( last->next = cur->right )
    last = last->next;
    cur = cur->next;
    }
    }

    Hatem

    August 24, 2008 at 9:54 pm

  4. I’m terribly sorry, I forgot to mention that using additional variables or data structures (other than Next, the additional pointer) is not allowed!

    I updated the post, sorry Mr. Anonymous! My bad!

    AlaaShaker

    August 24, 2008 at 11:15 pm

  5. FIRST WINNER .. Hatem Abdel Ghani πŸ˜€
    Hatem got the right answer, first shot masha2allah .. seems you’re up to the ACM this year, huh? πŸ˜‰
    How are you? I really missed you on the first one .. you can still check it btw, the solution is posted separately ..

    Congrats .. any other winners?? πŸ˜€

    AlaaShaker

    August 24, 2008 at 11:22 pm

  6. Two questions:
    1- Are we allowed to use the implicit recursion stack, or is it considere a “data structure”?

    2- You included image seems to imply that a tree either has 2 children or no children, can I assume that?

    Mohamed Samy

    August 25, 2008 at 1:25 am

  7. Anyways, here’s my solution..It’s a bit unfair to participate ’cause I’m familiar with programming with continuation passing style, so It came quickly to my mind to use it πŸ™‚

    it it correct?

    //The language is C#
    ListNode treeToList(TreeNode t)
    {
    return treeToList(t, null);
    }
    ListNode treeToList(TreeNode t, TreeNode continuation)
    {
    if(t==null)
    return continuation;
    ListNode n = new ListNode();
    if(t.left == null && t.right==null)
    {
    n.ch = t.ch;
    n.next = continuation;
    return n;
    }
    if(t.left == null)
    {
    n.ch = t.ch;
    n.next = treeToList(t.right, continuation);
    }
    if(t.right== null)
    {
    n.ch = t.ch;
    n.next = treeToList(t.right, continuation);
    }
    // both left and right branches (shudder!)
    ListNode n1 = new ListNode();
    n1.ch = left.ch;
    n1.next = treeToList(t.left,
    treeToList(t.right, continuation));
    return n1;

    }

    Mohamed Samy

    August 25, 2008 at 1:34 am

  8. i will assume that next pointer is by default to NULL

    i will use this function

    void tree2linked(Node *head)
    {
    if (head->Right != NULL)
    {
    head->Right->next = head->Left;
    tree2linked(head->Right);
    }
    if (head->Left != NULL)
    {
    Node *x;
    Node *temp = head;
    do
    {
    if (temp->next == NULL)
    {
    x = NULL;
    break;
    }
    x = temp->next->Right;
    temp = temp->next;
    }
    while (x == NULL);
    head->Left->next = x;
    tree2linked(head->Left);
    }
    }

    and in the main i will write this code

    head.next = head.Right;
    tree2linked(&head);

    TeCNoYoTTa

    August 25, 2008 at 8:50 am

  9. There is no more ACM, Alaa. I am an old man πŸ˜€

    But as you mentioned, the problem is easy; I am really curious how it was part of a Microsoft interview. Tell us more about that interview please.

    Hatem

    August 25, 2008 at 9:28 am

  10. I’m not sure if I completely get you Alaa! Are you saying, each node will have an extra member, that’s the Next pointer, and I’m allowed to only declare once extra pointer? That’s it? The rest are just statements? I’m trying to get things clear that’s all.

    anonymous

    August 25, 2008 at 11:08 am

  11. To Mohamed Samy:
    Regarding your questions: (1) No (2) No πŸ˜€

    Honestly tracing your solution was pretty hard, it’s the closest to mine except that I don’t use recursion – just a simple O(n) linear loop.

    One thing about your solution, I do NOT want to create another linked list .. I just want to alter the structure. So, instead of having just Left and Right pointers, I want a third pointer that points to the Next node in that row-by-row fashion. In other words, it’s NOT a traverse-and-construct-a-link-list problem, if you know what I mean ..

    AlaaShaker

    August 25, 2008 at 12:10 pm

  12. To TeCNoYoTTa:
    Thanks for your solution, but please, try to run your code first, and with several test cases. I’m sorry, but I won’t be able to build projects, and write a whole new program just to test your function.

    Anyway, your code has fatal errors. In addition to that, I suggest you read the problem again ‘coz you are linking in a totally wrong way.
    It’s A > B > C > D > … please check it!

    AlaaShaker

    August 25, 2008 at 12:13 pm

  13. To Hatem:
    Yeah, I had an interview for the new dev-center in CMIC. Actually, it was four interviews back-to-back. I passed’em all a7l, but the hiring was for one seat, that eventually was left to a senior candidate πŸ˜€
    I will blog about that soon isA, but I’ll post the problems first so I could link to them .. LOOOL

    And, man, you’re not old .. we’ll be brutally needing your help in the ACM next year (A)

    AlaaShaker

    August 25, 2008 at 12:16 pm

  14. To The-Insisting-on-being-anonymous:
    Nop. In your code, create extra pointers to help you solve the problem and write those statements as much as you please. I don’t want you to use a stack, queue, linked list, or any other data structures.

    To be exact:
    (1) Alter the struct Node to hold an third pointer Next.
    (2) Traverse the tree in a linear, row-by-row fashion, to assign the proper values of that pointer, Next, without messing with the tree.

    (Assume Next is set to NULL, initially. Just traverse the tree, and correct that πŸ˜€ That’s all .. )

    AlaaShaker

    August 25, 2008 at 12:22 pm

  15. well, I wrote some code.. check it..
    Hope the code looks understandable cause I am writing it in a not very good state..

    void TraverseToList(Node *root)
    {
    Node *current = root;
    Node *otherBranch = NULL;

    while(1)
    {
    if(current == otherBranch)
    break;

    if(current->Left != NULL)
    current->Left->Next = current->Right;

    if(current->Left != NULL && otherBranch == NULL)
    {
    current->Next = current->Left;
    otherBranch = current->Right;
    current = current->Next;
    }
    else if(otherBranch != NULL)
    {
    if(current->Next == NULL)
    {
    current->Next = otherBranch;
    }
    if(current->Left != NULL)
    otherBranch = current->Left;
    else if(current->Right != NULL)
    otherBranch = current->Right;

    current = current->Next;
    }
    else if(current->Left == NULL && otherBranch == NULL)
    {
    current->Next = current->Right;
    current = current->Next;
    }
    }
    }

    Roaa

    August 25, 2008 at 4:02 pm

  16. How about this ; )

    // Traditional breadth first search with a queue
    // but the queue recycles tree nodes
    Node listify(Node n)
    {
    Node toAdd = n;
    Node first = n, last = n;

    if(n.left!=null)
    enqueue(ref first, ref last, n.left);
    if(n.right!=null)
    enqueue(ref first, ref last, n.right);

    while(first!=null)
    {
    Node current = dequeue(ref first, ref last);
    toAdd.next = current;
    toAdd = toAdd.next;
    if(current.left!=null)
    enqueue(ref first, ref last, current.left);
    if(current.right!=null)
    enqueue(ref first, ref last, current.right);
    }
    return n;

    }
    void enqueue(ref Node first, ref node last, Node element)
    {
    if(first == null)
    first = last = element;
    else
    {
    element.next = null;
    last.next = element;
    last = element;
    }
    }
    Node dequeue(ref Node first, ref node last)
    {
    if(first == null)
    throw EmptyQueueException();
    else
    {
    Node element = first;
    first = first.next;
    return element;
    }
    }

    Mohamed Samy

    August 25, 2008 at 5:40 pm

  17. Man, tracing code this way is very painful πŸ˜₯

    To Roaa:
    Your solution is 90% correct – I won’t give that a YES, but I won’t post it ‘coz ppl will cheat .. loool
    In the problem statement, it says “You have a binary tree, not necessarily complete ..”

    Your code will crash for not handling that .. try again with a few leaves off πŸ˜‰
    Actually, that’s like 200% correct considering ur state .. salamtik πŸ˜€

    AlaaShaker

    August 25, 2008 at 6:55 pm

  18. ANOTHER CORRECT SOLUTION goes to …
    Mohamed Samy

    Simple, straight forward. Man, I enjoyed tracing such brilliant code, even though it was killing me ‘coz you build links, break them, set them again, looooool

    Bullet-proof .. again πŸ˜‰

    AlaaShaker

    August 25, 2008 at 6:57 pm

  19. I’m glad like liked the code. What I did was to get the standard code that does breadth first traversal and adapt it to the problem at hand. Not really the most efficient solution, but it works nonetheless.
    I appreciate the time you took to trace it πŸ™‚

    Mohamed Samy

    August 26, 2008 at 12:36 am

  20. OK.. HINTSSSSS:

    > Don’t go for recursion. Easier, go for a linear O(n) loop.
    > To link the tree, you can use two pointers. One stays on a Node, while the other moves β€œforward” to find it’s β€œNext” .. then move them both forward, and so on!
    > Don’t forget, the tree might be incomplete.

    (Note: Hints are relevant to my solution)
    I hope to get some correct answers now .. !! πŸ˜›

    AlaaShaker

    August 26, 2008 at 12:52 am

  21. I hope you don’t end this by tomorrow Alaa, will be posting about two solutions of which one is EXTREMELY TWISTED :]

    Metal_

    August 26, 2008 at 2:30 am

  22. To Metal: I really hope you won’t kill me tracing it .. loool

    AlaaShaker

    August 26, 2008 at 2:32 am

  23. Allah yesalemak.. Thanks πŸ™‚ ..
    I’m satisfied by the 90% in my current state, I’ll work on the 10% later πŸ˜€

    just a curious question.. were the question in the interview that specific? (with the Next & O(n) constraint?)
    asl I remember I was being asked that question fe one of the four interviews & I solved it using a queue πŸ™‚

    Roaa

    August 26, 2008 at 5:57 pm

  24. To Roaa:
    Take your time, el mohem te5efy πŸ˜€

    Yes, it was that specific. He drew me a binary tree on the board. Then, he drew the linkage horizontal using the Next pointers ..
    The linear part is not a constraint, I only said MY solution was linear πŸ˜€

    AlaaShaker

    August 26, 2008 at 6:03 pm

  25. #include
    #include
    using namespace std;
    struct Node
    {
    Node(int iValue)
    {
    pLeft = NULL;
    pRight = NULL;
    iData = iValue;
    }
    int iData;
    Node *pLeft;
    Node *pRight;
    };

    Node *pRoot;
    void ConstructTree ()
    {
    pRoot = new Node(0);
    pRoot->pLeft = new Node(1);
    pRoot->pRight = new Node(2);
    pRoot->pLeft->pLeft = new Node(3);
    pRoot->pRight->pRight = new Node(4);
    }
    void ConstructList()
    {
    queue Q;
    Node *pDummy = new Node(-1);
    Node *pCurrent = pDummy;
    Q.push(pRoot);
    while (!Q.empty())
    {
    Node *pNode = Q.front();
    Q.pop();
    pCurrent->pLeft = pNode;
    if (pNode->pLeft != NULL)
    Q.push(pNode->pLeft);
    if (pNode->pRight != NULL)
    Q.push(pNode->pRight);
    pCurrent = pNode;
    }
    if (pDummy)
    delete pDummy;
    }
    void PrintTree(Node *pRoot)
    {
    if (pRoot == NULL)
    return;
    PrintTree(pRoot->pLeft);
    cout <iData;
    PrintTree(pRoot->pRight);
    }
    void PrintList(Node *pRoot)
    {
    if (pRoot == NULL)
    return;
    cout <iData;
    PrintList(pRoot->pLeft);
    }
    void main()
    {
    ConstructTree();
    PrintTree(pRoot);
    ConstructList();
    PrintList(pRoot);
    }

    Mohammed Moussa

    August 26, 2008 at 6:32 pm

  26. To Mohammed Moussa:
    I didn’t try to test your code, I’m 100% sure it won’t be wrong .. except that you didn’t read the problem statement quite well πŸ˜€
    You used a Queue to solve it, piece of cake .. but you’re not allowed to do that πŸ˜€

    AlaaShaker

    August 26, 2008 at 6:42 pm

  27. ba3d keda 2eb2a 2oly 3ala el kol 7aga on the chat :D, 3ashan ana aslan sa2ltak 3aleha fe el chat 3ashan kaselt abos fe el problem ana 3agabetny el rasma fa 7aletha πŸ˜€ πŸ˜€

    Mohammed Moussa

    August 26, 2008 at 6:54 pm

  28. My solution uploaded at pastebin:
    http://pastebin.com/f5684b843

    I’m currently working on another reasonable straight forward one, so this is just a startup solution, to be more precise, an idea I wanted to finish that’s all.
    Highly complicated logic, trace at your own risk :] Don’t say I’ve not warned ya!

    Metal_

    August 27, 2008 at 1:16 am

  29. My second solution uploaded at pastebin:
    http://pastebin.com/f2bb02b97:

    Pasting it here too since it’s just few lines:

    // Metal_’s second algorithm for linking a binary tree.
    static void LinkBinaryTree(Node rootNode)
    {
    Node nodeUp = rootNode;
    Node nodeDown = rootNode;

    while (nodeUp != null)
    {
    if (nodeUp.left != null)
    {
    nodeDown = nodeDown.next = nodeUp.left;

    if (nodeUp.right != null)
    nodeDown = nodeDown.next = nodeUp.right;
    }
    else
    if (nodeUp.right != null)
    nodeDown = nodeDown.next = nodeUp.right;

    nodeUp = nodeUp.next;
    }
    }

    The major difference between my two algorithms is that first one doesn’t make use of the linking as it occurs(the precious next reference), so it’s next-independent, while the second one does! Which makes it more robust and faster :]

    Incase you are still wondering how the first one works, I cameup with a mathematical relation that predicts the path of the next node according to it’s order on the tree.
    The path is dependent on the
    -Current level .
    -Node’s order in that level.
    If someone is interested in knowing more about this let me know!

    *Both codes have been fully-tested with possible case, I don’t throw codes around :]

    Metal_

    August 27, 2008 at 12:20 pm

  30. To Metal_:
    Honestly, I tried tracing the 1st code, then I discovered it’s not the correct time to “dive” into it … LOL (it would be great if you could blog how you solved it that way, I’m interested)

    The 2nd solution is definitely correct, which makes you our THIRD WINNER πŸ˜€ Congrats … (Y)

    You made an extra check, doesn’t affect the output, it’s just a matter of obsessive code optimization (I’ll tell you about it when I post my solution isA).

    PS: I can’t edit comments .. just approve/spam/delete πŸ˜€

    AlaaShaker

    August 27, 2008 at 8:28 pm

  31. @Alaa
    You are right about the extra check, it was left from a previous one that handles the missing nodes kind of different anyway ..
    Here is the final code :]

    // Metal_’s second algorithm for linking a binary tree
    static void LinkBinaryTree(Node rootNode)
    {
    Node nodeUp = rootNode;
    Node nodeDown = rootNode;

    while (nodeUp != null)
    {
    if (nodeUp.left != null)
    nodeDown = nodeDown.next = nodeUp.left;

    if (nodeUp.right != null)
    nodeDown = nodeDown.next = nodeUp.right;

    nodeUp = nodeUp.next;
    }
    }

    Metal_

    August 27, 2008 at 11:07 pm

  32. // Ready to run 3ala tool :huh πŸ˜€

    #include
    using namespace std;

    struct Node
    {
    public:
    Node(char character)
    {
    ch = character;
    left = right = next = NULL ;
    }
    char ch;
    Node* left;
    Node* right;
    Node* next ;
    };

    Node* root ;

    void Initialize()
    {
    root->left = new Node(‘B’) ;
    root->right = new Node(‘C’) ;

    root->left->left = new Node(‘D’);
    root->left->right = new Node(‘E’);

    root->right->left = new Node(‘F’);
    root->right->right = new Node(‘G’);

    root->left->right->left = new Node(‘H’);
    root->left->right->right = new Node(‘I’);

    }
    void TreeToLinkedList( Node* parent )
    {
    Node* currentNode = parent ;
    Node* lastNode = parent ;

    while ( currentNode != NULL )
    {
    if( currentNode->left != NULL )
    {
    lastNode->next = currentNode->left ;
    lastNode = lastNode->next ;
    }
    if( currentNode->right != NULL )
    {
    lastNode->next = currentNode->right ;
    lastNode = lastNode->next ;
    }

    currentNode = currentNode->next ;

    }
    }
    void printList( Node* parent )
    {
    while( parent != NULL )
    {
    cout<ch<next ;
    }
    cout<<endl;
    }

    int main()
    {
    root = new Node(‘A’);
    Initialize();

    TreeToLinkedList( root ) ;

    printList( root ) ;
    return 0;
    }

    Mahmoud Osama

    August 28, 2008 at 7:17 pm

  33. To Mahmoud Osama:
    Judge – Answer: YES πŸ˜›

    Congrats to Mahmoud, our FOURTH WINNER!!!

    AlaaShaker

    August 28, 2008 at 7:55 pm

  34. Yessss, 3ayzeen mas2alet Geometry ba2a el marra el gaya πŸ˜€ πŸ˜€

    Mahmoud Osama

    August 28, 2008 at 7:56 pm

  35. […] SOLVED [Problem of the Week] This week’s problem was was pretty easy – obviously for ACMers […]


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: