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]
Rating: 9.3/10 (19 votes cast)
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”;
    LinkedList q = new LinkedList();
    q.add(this);
    q.add(d);
    while(!q.isEmpty())
    {
    Object o = q.remove();
    if(d.equals(o))
    {
    if (q.isEmpty())
    break;
    q.add(d);
    s.push(d);
    }
    else
    {
    Node n = (Node) o;
    s.push(n);
    if(n.left != null)
    q.add(n.left);
    if(n.right != null)
    q.add(n.right);
    }
    }
    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]]