Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Reverse Level Order Traversal

Objec­tive: - Given a binary tree, Do the reverse level order tra­ver­sal. In our ear­lier post we have seen nor­mal Level Order Tra­ver­sal. In reverse level order tra­ver­sal we first need to print the last level fol­lowed by sec­ond last level up to the root, which is the first level.

Exam­ple:

Reverse-Level-Order-Traversal

Reverse-Level-Order-Traversal

 Approach: Use Stack

  • Use the Queue and do the level order tra­ver­sal, read “Level Order Tra­ver­sal” First if you doesn’t know the technique.
  • Instead of print­ing the Node, keep adding it to Stack.
  • At the End print all the nodes from Stack, it will be in reverse order than nor­mal level order traversal.

Code:


Out­put:

7 6 5 4 3 2 1

You may also like...

  • Niran­jan B Subramanian

    should’nt the out­put be like this

    4 5 6 7 2 3 1

  • Chan­dra Gopalaiah

    queue inser­tion order needs to be changed. First insert right child and then left child

    • tuto­ri­al­hori­zon

      Reverse level order means that we will print the last level first and then from there we will go to the root. It does not mat­ter actu­ally whether in a par­tic­u­lar level which node you insert first, left or right.

      • Rakesh Venkatesh

        It does mat­ter for the order in which you insert the node into stack. The nodes should always be printed from left to right