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
Ranganathg's Blog 
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 ..
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;
}
@Mudit,
Good one buddy!
@Vasu,
Thanks for the neat code :). I think your solution is similar to Mudit’s solution, Am I correct?
If only more people could read this..