바이너리 트리 사전 주문 트래버설

Problem Statement

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

Preorder Traversal follows:

Root

↓

Left

↓

Right

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Moving Towards the Optimal Iterative Approach

Instead of recursion,

we can use a stack.

Since preorder visits:

Root

↓

Left

↓

Right

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

To visit:

Left First

Enter fullscreen mode Exit fullscreen mode

push:

Right First

↓

Left Second

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Dry Run

        1
       / \
      2   3
     / \
    4   5

Enter fullscreen mode Exit fullscreen mode

Stack:

1

Enter fullscreen mode Exit fullscreen mode

Visit:

1

Enter fullscreen mode Exit fullscreen mode

Push:

3

2

Enter fullscreen mode Exit fullscreen mode

Visit:

2

Enter fullscreen mode Exit fullscreen mode

Push:

5

4

Enter fullscreen mode Exit fullscreen mode

Traversal:

1

↓

2

↓

4

↓

5

↓

3

Enter fullscreen mode Exit fullscreen mode

Answer:

[1,2,4,5,3]

Enter fullscreen mode Exit fullscreen mode

Why Stack Works?

A stack processes the most recently added node first.

By pushing:

Right Child

↓

Left Child

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Mental Model

Root

↓

Stack

↓

Right

↓

Left

↓

Left Pops First

Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

“Preorder Traversal”

your brain should immediately think:

Root → Left → Right + Stack