Binary Tree PreOrder Traversal

leetcode.com

Problem Statement

Given the root of a binary tree, return its preorder traversal.

Preorder Traversal follows:

Root

↓

Left

↓

Right

---

Brute Force Intuition

In an interview, you can explain it like this:

Visit the current node first, then recursively traverse the left subtree followed by the right subtree.

Recursion naturally follows the preorder sequence.

Complexity

• Time Complexity: O(N)
• Space Complexity: O(H)

Where:

• N = Number of Nodes
• H = Height of Tree

Recursive Code

class Solution {

    public List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> ans = new ArrayList<>();

        preorder(root, ans);

        return ans;
    }

    private void preorder(TreeNode root,
                          List<Integer> ans) {

        if (root == null)
            return;

        ans.add(root.val);

        preorder(root.left, ans);

        preorder(root.right, ans);
    }
}

---

Moving Towards the Optimal Iterative Approach

Instead of recursion,

we can use a stack.

Since preorder visits:

Root

↓

Left

↓

Right

we should process the root immediately.

To ensure the left subtree is processed first,

push the right child before the left child.

---

Pattern Recognition

Whenever you see:

• Preorder Traversal
• Simulate Recursion

Think:

Stack

---

Key Observation

Stack follows:

LIFO

To visit:

Left First

push:

Right First

↓

Left Second

so that left is popped first.

---

Optimal Java Solution

class Solution {

    public List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> ans = new ArrayList<>();

        if (root == null)
            return ans;

        Stack<TreeNode> st = new Stack<>();

        st.push(root);

        while (!st.isEmpty()) {

            TreeNode node = st.pop();

            ans.add(node.val);

            if (node.right != null)
                st.push(node.right);

            if (node.left != null)
                st.push(node.left);
        }

        return ans;
    }
}

---

Dry Run

        1
       / \
      2   3
     / \
    4   5

Stack:

1

Visit:

1

Push:

3

2

Visit:

2

Push:

5

4

Traversal:

1

↓

2

↓

4

↓

5

↓

3

Answer:

[1,2,4,5,3]

---

Why Stack Works?

A stack processes the most recently added node first.

By pushing:

Right Child

↓

Left Child

the left child is processed before the right child, preserving preorder traversal.

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(H)

---

Interview One-Liner

Push the root into a stack, process it immediately, then push the right child followed by the left child so the left subtree is visited first.

---

Pattern Learned

Root

↓

Left

↓

Right

Similar Problems

• Preorder Traversal
• Flatten Binary Tree to Linked List
• Serialize Binary Tree
• N-ary Tree Preorder Traversal

---

Memory Trick

Visit Root

↓

Push Right

↓

Push Left

↓

Repeat

Mental Model

Root

↓

Stack

↓

Right

↓

Left

↓

Left Pops First

Whenever you hear:

"Preorder Traversal"

your brain should immediately think:

Root → Left → Right + Stack