## 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

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. 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. 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;

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

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

currentNode = currentNode -> next;
}

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

freeMemory(first);
}

{
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. 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. May 29, 2010 at 1:38 am

If only more people could read this..