RSS

Interview Question : Print nodes of a Binary Tree level order from leaves to root

08 May

I think most of you might know about Breadth First Search (BFS), in which you print nodes of a tree from root to leaves. Now there is a small change to the way the nodes are printed. Lets say given a binary tree, I want the nodes to be printed level order but from leaves to root

Eg :  consider the binary tree at this locations http://www.cs.mcgill.ca/~jeromew/comp252/images/Binary_tree.pn

Now you need to print : 5 11 4 2 6 9 7 5 2

Advertisements
 
4 Comments

Posted by on May 8, 2010 in Algorithms

 

Tags: , , ,

4 responses to “Interview Question : Print nodes of a Binary Tree level order from leaves to root

  1. mudit

    May 8, 2010 at 8:09 pm

    Modifying BFS a bit …

    take a queue ..

    start from the root .. put it in the queue .. but while adding the children in the queue ..first add right node (children) and then the left node .. keep doing it and build a queue ..

    just print the queue from the back side.. and there you go …

    for the same example .. my queue would look like this …

    2 5 7 9 6 2 4 11 5

    start printing from rear end ..

     
  2. Vasu

    May 8, 2010 at 8:21 pm

    Struct BinaryTreeNode
    {
    int value;
    Struct BinaryTreeNode * left;
    Struct BinaryTreeNode * right;
    }

    Struct Node
    {
    BinaryTreeNode * element;
    Struct Node * previous;
    Struct Node * next;
    }

    Node *first = null;
    Node *tail = null;

    Node * constructLeavesToRootList(BinaryTreeNode root)
    {

    if(root == NULL) return;

    Node * currentNode = addNodeToList(root);

    while(currentNode != NULL)
    {
    if(currentNode -> element -> right != NULL)
    addNodeToList(currentNode->element->right);

    if(currentNode -> element -> left != NULL )
    addNodeToList(currentNode->element->left);

    currentNode = currentNode -> next;
    }

    printlist (tail); // print the elements from tail by going back

    freeMemory(first);
    }

    Node * currentNode addNodeToList(BinaryTreeNode btnode)
    {
    Node * temp = (Node *) malloc(sizeof(Node));
    temp->element = btnode;
    temp->next = null;
    temp->previous = tail;
    if(tail != null)
    tail->next = temp;
    tail = temp;
    if(first== null)
    first = temp;
    }

     
  3. ranganathg

    May 9, 2010 at 10:40 am

    @Mudit,
    Good one buddy!

    @Vasu,
    Thanks for the neat code :). I think your solution is similar to Mudit’s solution, Am I correct?

     
  4. Beulah Dobson

    May 29, 2010 at 1:38 am

    If only more people could read this..

     

Leave a Reply

Please log in using one of these methods to post your comment:

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: