# Programming Interview Questions 21: Tree Reverse Level Order Print

This is very similar to the previous post level order print. We again print the tree in level order, but now starting from bottom level to the root. Using the same tree as before:

The output should be:
4 5 6
2 3
1

The solution of this problem is similar to level order print. We start a breadth first search (BFS) from the root of the tree and push each node to a queue. We don’t print any node at this point because we want to output bottom up, but BFS progresses from top to bottom. Printing will be take place a separate loop after completing breadth first search. We also count the number of nodes in each level and push them to a stack, in order to print the new lines in correct places. So after completion of BFS we have the following two data structures:

Queue of nodes: [1, 2, 3, 4, 5, 6]. This queue is constructed by BFS from top to bottom and left to right.
Stack of node counts at each level: [3, 2, 1]. Note that since this is a stack the first element is the node count at the deepest level, and the last count is always 1 which corresponds to the root of the tree.

After constructing these data structures, the nodes we want to print as the first line of output are at the end of the queue. And the number of nodes to print is at the top of the stack. So we start a loop where at each iteration we pop an element from the stack and print that many number of nodes from the end of the queue. Using the example tree above, the first line of the output contains 3 nodes, the first element in the stack. And the nodes to print are the 3 nodes at the end of the queue, which is [4, 5, 6]. The second line of the output contains 2 nodes, the second value in the stack. These are the 2 nodes in the queue that are just before the first line nodes, namely [2, 3]. Finally, the number of nodes in the last line is at the end of the stack, which is 1. And the node to print is at the beginning of the queue, the value 1.

Here is the code:

```def reverseLevelOrderPrint(tree): if not tree: return nodes=[tree] #queue levelCount=collections.deque([1]) #stack currentCount, nextCount = 1, 0 i=0 while i<len(nodes): currentNode=nodes[i] currentCount-=1 if currentNode.left: nodes.append(currentNode.left) nextCount+=1 if currentNode.right: nodes.append(currentNode.right) nextCount+=1 if currentCount==0: #finished this level if nextCount==0: #no more nodes at next level break #continue with next level levelCount.appendleft(nextCount) currentCount, nextCount = nextCount, currentCount i+=1 printIndex=len(nodes) for count in levelCount: output=nodes[printIndex-count:printIndex] print ' '.join(map(str, output)), '\n', printIndex-=count```

This is a great question that uses the most fundamental data structures: tree, stack, and queue.

VN:F [1.9.22_1171]
Programming Interview Questions 21: Tree Reverse Level Order Print, 9.3 out of 10 based on 19 ratings
This entry was posted in Programming Interview. Bookmark the permalink.
• http://dpsm.wordpress.com David

Hi Arden,

There is a little error in your algorithm where if the same tree above doesn’t contain node 4 it will provide the wrong result. See bellow the proper algorithm:

while i 0:
#finished this level
levelCount.appendleft(nextCount)
currentCount, nextCount = nextCount, currentCount
else:
#no more nodes at next level
break
i+=1

Good job with putting these questions/answers together :)

David

• Arden

Thanks a lot for pointing out the bug David! I updated the code. I’m glad that you like the articles..

• http://dpsm.wordpress.com David
```while i 0:
#finished this level
levelCount.appendleft(nextCount)
currentCount, nextCount = nextCount, currentCount
else:
#no more nodes at next level
break
i+=1
```
• Abhishek Srinath

C++ solution. Please check and comment if its wrong at some point

void printNodesByReverseLevels(struct node *root)
{
queue nodes;
deque allNodes;
stack countAtLevelI;
int currentLevelCount = 0;
int nextLevelCount = 0;
if(root == NULL)
{
return;
}
else
{
nodes.push(root);
allNodes.push_back(root);
currentLevelCount = 1;
countAtLevelI.push(currentLevelCount);

while(!nodes.empty())
{
NODE cur = nodes.front();
nodes.pop();
currentLevelCount–;
if(cur->left != NULL)
{
nodes.push(cur->left);
allNodes.push_back(cur->left);
nextLevelCount++;
}
if(cur->right != NULL)
{
nodes.push(cur->right);
allNodes.push_back(cur->right);
nextLevelCount++;
}
if(currentLevelCount == 0)
{
currentLevelCount = nextLevelCount;
countAtLevelI.push(currentLevelCount);
nextLevelCount = 0;
}
}

while(!countAtLevelI.empty())
{
int countAtI = countAtLevelI.top();
countAtLevelI.pop();

// this is to make sure the nodes are printed in the left to right order.

for(int j = allNodes.size() – countAtI;j < allNodes.size();j++)
{
cout <value << 't';
}
for(int i = 0;i < countAtI;i++)
{

allNodes.pop_back();
}
cout << endl;
}

}
}

• Zeus

Here my code prints the tree level by level as well as upside down

int counter=0;// to count the toatl no. of elments in the tree

void tree::print_treeupsidedown_levelbylevel(int *array)

{

int j=2;

int next=j;

int temp=0;

while(j<2*counter)

{

if(array[j]==0)

break;

while(array[j]!=-1)

{

j++;

}

for(int i=next,k=j-1 ;i=0;i–)

{

if(array[i]>0)

printf(“%d “,array[i]);

if(array[i]==-1)

printf(“n”);

}

}

void tree::BFS()

{

queuep;

node *leaf=root;

int array[2*counter];

for(int i=0;ival=0;

newline->left=NULL;

newline->right=NULL;

newline->parent=NULL;

p.push(leaf);

p.push(newline);

while(!p.empty())

{

leaf=p.front();

if(leaf==newline)

{

printf(“n”);

p.pop();

if(!p.empty())

p.push(newline);

array[count++]=-1;

}

else

{

cout<val<val;

if(leaf->left!=NULL)

{

p.push(leaf->left);

}

if(leaf->right!=NULL)

{

p.push(leaf->right);

}

p.pop();

}

}

delete newline;

print_treeupsidedown_levelbylevel(array);

}

Here in my code the function BFS prints the tree level by level, which

also fills the data in an int array for printing the tree upside down.

(note there is a bit of swapping is used while printing the tree upside down

which helps to achieve our goal).

if the swaping is not performed then for a tree like

8

/

1 12

/

5 9

/

4 7

/

6

o/p will be

6

7 4

9 5

12 1

8

but the o/p has to be

6

4 7

5 9

1 12

8

this the reason why swapping part wass needed in that array.

• İbrahim Aygül

Hi Arden,
You say that nodes is queue. but accesing to a queue like “nodes[printIndex-count:printIndex]” is not allowed.
We cant say we are using a queue structure here. it is just a dynamic list provided by python. (As far as I understand; I do not know python well)

• Guest

Easier implementation in Java:

private void PrintRev()
{
Stack s = new Stack();
String d = “delim”;
while(!q.isEmpty())
{
Object o = q.remove();
if(d.equals(o))
{
if (q.isEmpty())
break;
s.push(d);
}
else
{
Node n = (Node) o;
s.push(n);
if(n.left != null)
if(n.right != null)
}
}
while(!s.empty())
{
Object o = s.pop();
if(d.equals(o))
{
System.out.println();
}
else
{
Node n = (Node) o;
System.out.print(n.value + ” “);
}
}
}

• presman

Scan current level ( starting with root ). collect values of the elements. also, collect in a separate stack all values of the current elements’ children. once done with current level, start going through the children. at the end, reverse the list of vales.

• ctall

In C;

typedef struct T {struct _T *l; struct _T *r; int v;} T;
f(r, R)T *r;{
if (r->l) f(r->l, 0);
if (r->r) f(r->r, R);
printf(R?”%dn”:”%d “, r->v);
}

• Matt Auerbach

Just curious, why can’t we use a DFS? Shouldn’t that print the deepest elements first?

• Shravan Durvasula

No. Irrespective of whether it is in-order, pre-order, post-order DFS wont be able to traverse it level by level, which happens naturally with BFS.

• Mythri Nagaraju

what is the time complexity for this?

I wrote this code using only a stack, but the time complexity is O(n^2):

def reverse_level_order(self,root):
stack = []
stack.append([root])
top = stack[len(stack)-1]
while(len(top) > 0):
top = stack[len(stack)-1]
list = []
for elem in top:
if elem.left:

list.append(elem.left)

if elem.right:

list.append(elem.right)

if not list: break
stack.append(list)
for i in range(len(stack)-1,-1,-1):
print [elem.data for elem in stack[i]]