Introduction

LeetCode 144 – Binary Tree Preorder Traversal is one of the most important beginner-friendly tree traversal problems in Data Structures and Algorithms.

This problem helps you understand:

1. Binary Tree Traversal
2. Depth First Search (DFS)
3. Recursion
4. Stack-based traversal
5. Tree traversal patterns

Preorder traversal is widely used in:

1. Tree copying
2. Serialization
3. Expression trees
4. DFS-based problems
5. Hierarchical data processing

It is also one of the most commonly asked tree problems in coding interviews.

Problem Link

🔗 Problem

LeetCode 144: Binary Tree Preorder Traversal

Official Problem:

LeetCode Problem Link

Problem Statement

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

What is Preorder Traversal?

In preorder traversal, nodes are visited in this order:

The root node is processed first before traversing subtrees.

Example

Input

Tree Structure:

Preorder Traversal

Traversal order:

Output:

Recursive Approach (Most Common)

Intuition

In preorder traversal:

1. Visit current node
2. Traverse left subtree
3. Traverse right subtree

This naturally fits recursion because trees themselves are recursive structures.

Recursive DFS Visualization

Traversal pattern:

Recursive function:

Java Recursive Solution

Dry Run – Recursive Approach

Tree:

Step 1

Start at:

Add:

Move right to:

Step 2

Add:

Move left to:

Step 3

Add:

Final Answer

Time Complexity – Recursive

Time Complexity

Every node is visited once.

Space Complexity

Where:

1. H = height of tree
2. Recursive call stack uses extra space

Worst case:

for skewed trees.

Iterative Approach (Interview Follow-Up)

The follow-up asks:

Can you solve it iteratively?

Yes.

We use a stack to simulate recursion.

Iterative Preorder Intuition

Preorder traversal order is:

Using a stack:

1. Process current node immediately
2. Push right child first
3. Push left child second

Why?

Because stacks follow:

So left subtree gets processed first.

Stack-Based Iterative Logic

Algorithm

1. Push root into stack.
2. Pop node.
3. Add node value.
4. Push right child.
5. Push left child.
6. Repeat until stack becomes empty.

Java Iterative Solution

Dry Run – Iterative Approach

Tree:

Step 1

Push:

Step 2

Pop:

Add:

Push right child:

Step 3

Pop:

Add:

Push left child:

Step 4

Pop:

Add:

Final Answer

Comparison of Approaches

Interview Explanation

In interviews, explain:

Preorder traversal processes nodes in Root → Left → Right order. Recursion naturally handles this traversal. Iteratively, we use a stack and push the right child before the left child so the left subtree gets processed first.

This demonstrates strong DFS and stack understanding.

Common Mistakes

1. Wrong Traversal Order

Incorrect:

That is inorder traversal.

Correct preorder:

2. Forgetting Null Base Case

Always check:

3. Wrong Stack Push Order

For iterative traversal:

1. Push right first
2. Push left second

Otherwise traversal order becomes incorrect.

FAQs

Q1. Why is preorder traversal useful?

It is heavily used in:

1. Tree cloning
2. Serialization
3. DFS traversal
4. Expression trees

Q2. Which approach is preferred in interviews?

Recursive is simpler.

Iterative is often asked as a follow-up.

Q3. Can preorder traversal be done without stack or recursion?

Yes.

Using Morris Traversal.

Q4. What is the difference between preorder, inorder, and postorder?

Bonus: Morris Preorder Traversal

Morris traversal performs preorder traversal using:

extra space.

This is considered an advanced interview topic.

Conclusion

LeetCode 144 is one of the most fundamental binary tree traversal problems.

It teaches:

1. DFS traversal
2. Recursion
3. Stack simulation
4. Binary tree fundamentals

The key preorder pattern is:

Mastering this traversal builds a strong foundation for advanced tree problems such as:

1. Tree serialization
2. DFS-based problems
3. Tree reconstruction
4. Expression trees
5. Morris traversal