Reverse Level-Order Traversal
In this lesson, you will learn how to implement reverse level-order traversal of a binary tree in Python.
We'll cover the following...
This lesson will be an extension of the previous lesson. In this lesson, we will go over how to perform a reverse level-order traversal in a binary tree. We then code a solution in Python building on our binary tree class.
Below is an example of reverse level-order traversal of a binary tree:
Algorithm
To solve this problem, we’ll use a queue again just like we did with level-order traversal, but with a slight tweak; we’ll enqueue the right child before the left child. Additionally, we will use a stack. The algorithm starts with enqueuing the root node. As we traverse the tree, we dequeue the nodes from the queue and push them to the stack. After we push a node on to the stack, we check for its children, and if they are present, we enqueue them. This process is repeated until the queue becomes empty. In the end, popping the element from the stack will ...