ProgramGuru.org

ProgramGuru.org

Postorder Traversal of a Binary Tree using Iteration

Visualization

Algorithm Steps

  1. Start with the root node of the binary tree.
  2. If the tree is empty, return an empty result.
  3. Initialize two stacks, stack1 and stack2.
  4. Push the root node onto stack1.
  5. While stack1 is not empty, pop a node from it and push that node onto stack2.
  6. If the popped node has a left child, push it onto stack1; if it has a right child, push it onto stack1.
  7. After processing all nodes, pop all nodes from stack2 and record their values. This produces the postorder traversal.

Postorder 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 postorderTraversal(root):
    if not root:
        return []
    stack1, stack2 = [root], []
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    result = []
    while stack2:
        result.append(stack2.pop().val)
    return result

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