Reverse level order traversal in Kotlin | Binary Tree

Reverse level order traversal in a binary tree means traversing the nodes of the tree from the last level to the first level, i.e., from the bottom to the top.

To perform a reverse level order traversal, we can use a queue to store the nodes of the tree level by level. However, instead of processing the nodes in the order they are inserted into the queue, we will process them in the reverse order.

Here’s the algorithm to perform a reverse level order traversal in a binary tree:

1. Create an empty queue and a stack.
2. Enqueue the root node into the queue.
3. While the queue is not empty, do the following: a. Dequeue a node from the queue and push it onto the stack. b. Enqueue the left child of the dequeued node if it exists. c. Enqueue the right child of the dequeued node if it exists.
4. Pop nodes from the stack and print them.

class Node(val data: Int, val left: Node? = null, val right: Node? = null)

The function takes a single input parameter, which is the root node of the binary tree. Note that the parameter is marked with a ? to indicate that it can be null, as the root of the tree could be empty.

if (root == null) return

We first check if the root node is null. If it is, we simply return from the function as there is nothing to traverse.

val queue: Queue<Node> = LinkedList()
val stack = Stack<Node>()
queue.add(root)

We then create an empty queue and a stack to store the nodes of the tree. and then we add the root node to the queue to start the traversal.

while (queue.isNotEmpty()) {
        val node = queue.remove()
        stack.push(node)

        node.right?.let { queue.add(it) }
        node.left?.let { queue.add(it) }
    }

We use a while loop to process the nodes in the queue until it is empty. In each iteration of the loop, we dequeue a node from the queue and push it onto the stack. Then we enqueue the left and right child nodes of the dequeued node, if they exist.

while (stack.isNotEmpty()) {
        val node = stack.pop()
        print("${node.data} ")
    }

Once we have traversed all the nodes in the tree, we use another while loop to pop nodes from the stack and print their data values in reverse order.

import java.util.*

class Node(val data: Int, val left: Node? = null, val right: Node? = null)

fun reverseLevelOrderTraversal(root: Node?) {
    if (root == null) return

    val queue: Queue<Node> = LinkedList()
    val stack = Stack<Node>()

    queue.add(root)

    while (queue.isNotEmpty()) {
        val node = queue.remove()
        stack.push(node)

        node.right?.let { queue.add(it) }
        node.left?.let { queue.add(it) }
    }

    while (stack.isNotEmpty()) {
        val node = stack.pop()
        print("${node.data} ")
    }
}

// Example usage
fun main() {
    /*
    *          1
    *        /   \
    *       2     3
    *      / \   / \
    *     4   5 6   7
    * */

    val root = Node(
        1,
        Node(2, Node(4), Node(5)),
        Node(3, Node(6), Node(7))
    )

    reverseLevelOrderTraversal(root) // Output: 4 5 6 7 2 3 1
}