Finding PostOrder traversal from LevelOrder traversal without constructing the tree

Question

Given a binary tree where value of each internal node is 1 and leaf node is 0. Every internal node has exactly two children. Now given level order traversal of this tree return postorder traversal of the same tree.

This question can be easily solved if I construct a tree and then do its postorder traversal. Although it is O(n) time. But is it possible to print postOrder traversal without building up the tree.

I just realized that in-order traversal of these kind of trees will always produce sequence in the form 01010...01010. Maybe this fact can be used somehow. — Dialecticus

Steven Chen Steven Chen · Accepted Answer · 2014-11-09T06:52:03

It's definitely possible.

Considering it's a Full Binary Tree, once the number of nodes is determined, theoretically, the shape of tree is unique.

Deem the level order traversal as an array, for example, 1 2 3 4 5 6 7.

It represents such tree:

      1
   2     3
 4  5   6  7

What you want to get is the post order traversal: 4 5 2 6 7 3 1.

The first step is calculate how deep the tree was:

depth = ceil(log(2, LevelOrderArray.length))        // =3 for this example

after that, set up a counter = 0, and extract nodes from the bottom level of the original array, one by one:

for(i=0, i<LevelOrderArray.length, i++){
    postOrderArray[i] = LevelOrderArray[ 2 ^ (depth-1) +i ]       //4,5,....
    counter++;                                                //1,2,.....
}

But notice that once the counter can be divided by 2, that means you need to retrieve another node from upper level:

if(counter mod 2^1 == 0)
    postOrderArray[i] = LevelOrderArray[ 2 ^ (depth -2) + (++i) ]        // =2 here, 
//which is the node you need after 4 and 5, and get 3 after 6 and 7 at the 2nd round

Don't ++ the counter here, because the counter represents how many nodes you retrieved from the bottom level.

Every time 2^2 = 4 nodes was pop out, retrieve another node from 3rd level (counting from bottom)

if(counter mod 2^2 == 0)
    postOrderArray[i] = LevelOrderArray[ 2 ^ (depth -3) + (++i) ]        // =1

Every time 2^3 = 8 nodes was pop out, again, retrieve another node from 4th level

.... until the loop is finished.

It's not strict C++ code, only the concept. If you fully understand the algorithm, the value of tree nodes doesn't matter at all, even though there are all 0 and 1. The point is although you didn't build up the tree in program, but build it up in your mind instead, and convert it into algorithm.

Finding PostOrder traversal from LevelOrder traversal without constructing the tree

1 Answers