Reverse Level Order Traversal Of A Binary Tree

 

Ask a coding wizard of how amazing and iconic the Data structure and algorithms concept is!

Truly, DSA’s aspects are super interesting to learn and are extremely useful for every coder. 

Almost everything around us in this world has the essence of some DSA concept. 

For eg: The leaves of a particular tree follow the Fibonacci pattern whereas the tree itself is transformed into a concept called Binary tree. 

Isn’t it amazing how the world runs on mathematics and codes? 

To exemplify your excitement, we’re particularly going to pick out Binary tree as our main study and dive into its sub-aspect called reverse level order traversal.

Let us have a detailed look into the basics before we move to learn about the problem.

 

What is a binary tree?

A binary tree has parent nodes and each of those parent nodes can have two children nodes that are left and right nodes. Similar to the real-life tree, there is a source called “root” which is where the binary tree forms.

Under binary there are three important operations that are often performed and they are:

 

• Insertion: Helps to add elements into the binary tree in a desired order.

• Deletion: Similarly, helps to remove certain elements from the binary tree.

• Traversal: Aids to visit each node inside a Binary tree.

 

We will now have a brief look at tree traversal and its types to better understand what a reverse level order is.

What is tree traversal and its types?

Tree traversal as said before is a process where the nodes in a tree are visited once. However, there are different ways through which tree traversal can print the elements saved inside the nodes of the binary tree. 

The ways in which tree traversal can be executed are, 

• In-order traversal

• Post-order traversal

• Pre-order traversal

The most used type is In-order traversal and it helps the users to print the lastly added level first followed by the secondly added last level next. The procedure keeps going on. Technically, we will be printing from left to right.

When we speak about reverse level order traversal, we’re simply going to reverse the process of in-order traversal. That is, we will print the elements from right to left node.

How to reverse level order traversal?

To understand the concept practically, here’s a problem statement and its approaches to bring out the desired result.

Example question:

You are given an input and asked to give the output by reversing the level order traversal.

Input: 6, 3, 12, 8, 9

Output: 9, 8, 12, 3, 6

Approach 1: Recursion Depth First Search

Recursion is a method where the function will keep calling itself until the solution is given. Depth first search is a part of the recursion method where the backtracking process gets involved. 

To do this method, here are the steps:

• When you apply the recursion function, the “helper” will take in two main parameters of the tree that are levels and nodes. By this we mean, the helper will pick the present node and the level it is at.

• Now you should make sure that the binary tree isn’t void or null.

• In the output list, assess the levels and keep track of them. Then in the node level, pick the size of the levels. Now compare the node level size with output list level size.

• Now assess the current node’s value and append it to the level of the node.

• If you find children nodes In the node you’re currently picking, then apply traversal in recursive mode. That is helper(node -> left / node -> right, level + 1).

• The desired output will be given.

When you follow this method, the complexity of time would be O(N) similarly space would also be O(N). The letter N signifies the total count of the nodes in the tree.

 

Approach 2: Iteration Breadth-first search

Iteration simply means repeating a process until the outcome is given. Under this, the Breadth first search algorithm helps in exploring all the vertices present in the given graph. It will explore the distance between the source and the vertices.

To apply this method to reverse level order traversal, follow these steps:

• Create two queue data structures. These two queues’ job is to determine the node levels. That is, the first queue will find the current level of the node and the second queue will find the next level of the node.

• Moving, when the queue that finds the next level seems to be “not empty”, then apply these:

• The current level must be equal to the next level.

• You should then empty up the queue to the next level.

• Now via the queue with the current level, you should start the traversal. Then you should insert the node’s value in the final output list.

• Then simply insert the children node inside the queue.

• After these processes, you can reverse the levels.

The time complexity and space would be O(N) as the queues were used.

Interesting concept to know:

Now that we learnt how to reverse a tree traversal, there are certain other curious matters happening within the code. One thing we want to educate you about is Count Inversions otherwise known as Inversion counts.

Inversion counts check the number of steps taken to sort an array as per the desired method. Now that we wanted to reverse a tree traversal, the amount of steps we took to achieve it is called Count Inversions. 

Take a note of this amazing concept for it can be asked in various tech interviews.

Conclusion 

We’re finally wrapping this lesson with good news: You’ve made it! 

Learning coding is so much fun and we hope your knowledge has extended by today’s look into reverse level order traversal, the approaches and other needed facts.

Keep practicing coding problems, refresh your DSA knowledge and in no time, you will become a coding wizard.