ProgramGuru.org

ProgramGuru.org

Reverse Level Order Traversal of a Binary Tree using Iteration

Visualization

Algorithm Steps

  1. If the binary tree is empty, return an empty result.
  2. Initialize an empty queue and push the root node onto it.
  3. Initialize an empty stack.
  4. While the queue is not empty, dequeue a node from the front, push it onto the stack, then enqueue its right child (if it exists) followed by its left child (if it exists).
  5. Once the queue is empty, pop all nodes from the stack and record their values. This produces the reverse level order traversal.

Reverse Level Order Traversal of a Binary Tree using Iteration - Code Examples Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def reverseLevelOrder(root):
    if not root:
        return []
    from collections import deque
    queue = deque([root])
    stack = []
    while queue:
        node = queue.popleft()
        stack.append(node)
        if node.right:
            queue.append(node.right)
        if node.left:
            queue.append(node.left)
    result = []
    while stack:
        result.append(stack.pop().val)
    return result

if __name__ == '__main__':
    # Construct binary tree:
    #        1
    #       / \
    #      2   3
    #     / \
    #    4   5
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(reverseLevelOrder(root))