Preorder Traversal of a Binary Tree using Iteration

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

Problem Statement❯

You are given the root of a binary tree. Your task is to perform a preorder traversal (root → left → right) using an iterative approach and return the list of visited node values. Preorder traversal starts at the root, visits the left subtree, and then the right subtree. Implement the logic using a stack instead of recursion.

Examples❯

Input Tree Visual Structure Expected Output Case Type
[1, 2, 3, 4, 5, null, 6]
[1, 2, 4, 5, 3, 6] Normal Tree
[] [] Empty Tree
[1]
[1] Single Node
[1, 2, null, 3]
[1, 2, 3] Left-skewed Tree
[1, null, 2, null, 3]
[1, 2, 3] Right-skewed Tree

Visualization Player

Solution❯

Case 1: Normal Binary Tree

In a regular binary tree with both left and right children, the iterative preorder traversal visits the root first, then moves left, then right. A stack helps simulate the recursive behavior. First, push the root. Then, for every popped node, push the right child (so it is visited later) and then the left child (so it is visited next).

Case 2: Empty Tree

If the tree is empty (i.e., the root is null), then there are no nodes to visit. In this case, the output is simply an empty list []. This is the base case and should be handled first before any stack operations.

Case 3: Single Node Tree

When the tree has only one node, it becomes both the root and the leaf. So, the traversal visits this only node and returns its value. The output will be a single-element list containing that node's value.

Case 4: Left-skewed Tree

In a left-skewed tree, each node only has a left child. The traversal moves down the left edge of the tree starting from the root. The stack grows linearly as each left child is pushed after its parent. The output will be a list of values from the root down to the deepest left child.

Case 5: Right-skewed Tree

In a right-skewed tree, each node only has a right child. The iterative traversal still starts with the root, but since there are no left children, it just keeps pushing right children to the stack. The stack will always hold one node at a time, and the output will be a list of values from the root down the right chain.

Using a stack ensures we control the traversal manually, mimicking recursion by explicitly handling the order of visiting nodes. This approach is especially useful in systems where recursion depth is limited.

Algorithm Steps❯

  1. Start with the root node of the binary tree.
  2. If the tree is empty, return an empty result.
  3. Initialize a stack and push the root node onto it.
  4. While the stack is not empty, pop a node from the stack and record its value.
  5. If the popped node has a right child, push it onto the stack.
  6. If the popped node has a left child, push it onto the stack.
  7. Repeat until the stack is empty. The recorded values form the preorder traversal.

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 preorderTraversal(root):
    if not root:
        return []
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    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(preorderTraversal(root))