Preorder Traversal of a Binary Tree using Iteration

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	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❯

Understanding the Problem

We are given a binary tree, and our task is to perform a preorder traversal iteratively. In preorder traversal, we visit the nodes in the order: root → left → right.

Normally, recursion is used for tree traversal, but here we want to do it without recursion, using a stack to simulate the recursive behavior. We must carefully push the nodes in the correct order to maintain the traversal sequence.

Let’s now break this problem down step by step using an example and also see how to handle edge cases like an empty tree or skewed trees.

Step-by-Step Solution with Example

Step 1: Choose an Example

Let’s take the binary tree:


      1
     /     2   3
   /   4   5

Expected preorder output: [1, 2, 4, 5, 3]

Step 2: Initialize Stack

We use a stack to help us traverse the tree. Initially, push the root node (1) to the stack.

Step 3: Traverse Using Stack

While the stack is not empty, do the following:

Pop the top node from the stack and visit it (i.e., add to result list).
Push the right child first (so it's visited later).
Then push the left child (so it's visited next).

Step 4: Execution on Example

Let’s trace the steps:

Stack = [1] → Pop 1 → Result = [1]
Push 3, then 2 → Stack = [3, 2]
Pop 2 → Result = [1, 2]
Push 5, then 4 → Stack = [3, 5, 4]
Pop 4 → Result = [1, 2, 4]
Pop 5 → Result = [1, 2, 4, 5]
Pop 3 → Result = [1, 2, 4, 5, 3]

Final output: [1, 2, 4, 5, 3]

Edge Cases

Case 1: Empty Tree

If the tree is empty (root is null), return an empty list: []. This must be checked before using the stack.

Case 2: Single Node Tree

If the tree has only one node, say 1, the result is just [1].

Case 3: Left-skewed Tree

Example:

The output will be: [1, 2, 3]. The stack will mimic deep recursion down the left edge.

Case 4: Right-skewed Tree

Example:


1
   2
       3

The output will be: [1, 2, 3]. Only right children are added and visited in order.

Finally

Iterative preorder traversal is a great way to avoid recursion depth limits and gives us better control over the traversal order. The key trick is always pushing the right child first, so the left child is processed next. This method works on any binary tree structure—balanced, skewed, or sparse—and handles all edge cases safely with just a few lines of robust logic.

Algorithm Steps❯

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

Code

C++

Python

Java

Rust

Kotlin

Swift

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

void preorder(TreeNode* root) {
    if (!root) return;
    printf("%d ", root->val);
    preorder(root->left);
    preorder(root->right);
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("Preorder Traversal: ");
    preorder(root);
    printf("\n");
    return 0;
}

⬅ Previous TopicPreorder Traversal of a Binary Tree using Recursion

Next Topic ⮕Inorder Traversal of a Binary Tree using Recursion

Comments

Loading comments...