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

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

## 4 thoughts on “Interview Question : Print nodes of a Binary Tree level order from leaves to root”

1. mudit says:

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 says:

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. ranganathg says:

@Mudit,
Good one buddy!

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