Preorder Traversal of a Binary Tree using Iteration

Problem and examples

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.

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

Explore Preorder Traversal of a Binary Tree - Iteration

Load an example or enter your own input. Use the player controls to follow each change.

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.

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.

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    cout << "Preorder Traversal: ";
    preorder(root);
    cout << endl;
    return 0;
}

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(root):
    if not root:
        return
    print(root.val, end=" ")
    preorder(root.left)
    preorder(root.right)

if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print("Preorder Traversal:", end=" ")
    preorder(root)
    print()

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Preorder {
    public static void preorder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        System.out.print("Preorder Traversal: ");
        preorder(root);
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function preorder(root) {
    if (!root) return;
    process.stdout.write(root.val + ' ');
    preorder(root.left);
    preorder(root.right);
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
process.stdout.write("Preorder Traversal: ");
preorder(root);
console.log();

Go implementation

package main

import "fmt"

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func preorder(root *TreeNode) {
    if root == nil {
        return
    }
    fmt.Print(root.val, " ")
    preorder(root.left)
    preorder(root.right)
}

func main() {
    root := &TreeNode{1, nil, nil}
    root.left = &TreeNode{2, &TreeNode{4, nil, nil}, &TreeNode{5, nil, nil}}
    root.right = &TreeNode{3, nil, nil}
    fmt.Print("Preorder Traversal: ")
    preorder(root)
    fmt.Println()
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn preorder(node: &Option<Box<TreeNode>>) {
    if let Some(n) = node {
        print!("{} ", n.val);
        preorder(&n.left);
        preorder(&n.right);
    }
}

fn main() {
    let tree = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode { val: 3, left: None, right: None })),
    }));
    print!("Preorder Traversal: ");
    preorder(&tree);
    println!();
}

Kotlin implementation

class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun preorder(node: TreeNode?) {
    if (node == null) return
    print("${node.value} ")
    preorder(node.left)
    preorder(node.right)
}

fun main() {
    val root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print("Preorder Traversal: ")
    preorder(root)
    println()
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func preorder(_ root: TreeNode?) {
    guard let node = root else { return }
    print(node.val, terminator: " ")
    preorder(node.left)
    preorder(node.right)
}

let root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left?.left = TreeNode(4)
root.left?.right = TreeNode(5)
print("Preorder Traversal:", terminator: " ")
preorder(root)
print()

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function preorder(root: TreeNode | null): void {
    if (!root) return;
    process.stdout.write(root.val + ' ');
    preorder(root.left);
    preorder(root.right);
}

const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5)),
    new TreeNode(3)
);
process.stdout.write("Preorder Traversal: ");
preorder(root);
console.log();