144. Binary Tree Preorder Traversal - Explanation

Description

You are given the root of a binary tree, return the preorder traversal of its nodes' values.

Example 1:

Input: root = [1,2,3,4,5,6,7]

Output: [1,2,4,5,3,6,7]

Example 2:

Input: root = [1,2,3,null,4,5,null]

Output: [1,2,4,3,5]

Example 3:

Input: root = []

Output: []

Constraints:

0 <= number of nodes in the tree <= 100
-100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Depth First Search

Intuition

Preorder traversal visits nodes in this exact order:

1. Node itself → 2. Left subtree → 3. Right subtree

So we simply start at the root and:

Record its value,
Recursively explore the left child,
Then recursively explore the right child.

This naturally follows the preorder definition, and recursion handles the tree structure automatically.

Algorithm

Create an empty result list res.
Define a recursive function:
- If the node is null, return.
- Add the node's value to res.
- Recurse on its left child.
- Recurse on its right child.
Call the function starting from the root.
Return res.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        def preorder(node):
            if not node:
                return

            res.append(node.val)
            preorder(node.left)
            preorder(node.right)

        preorder(root)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(n)$ space for the recursion stack.
- $O(n)$ space for the output array.

2. Iterative Depth First Search

Intuition

Preorder traversal follows the pattern:

Visit Node → Left → Right

Using a stack, we can simulate recursion.
The trick:

Whenever we visit a node, we immediately record its value (preorder rule).
Then we push the right child first, because the stack is LIFO and we want to process the left child next.
Move to the left child and repeat.
If we reach a null left child, pop from the stack to continue with the right subtree.

This preserves the exact preorder sequence without recursion.

Algorithm

Initialize an empty list res for the result.
Create an empty stack.
Set cur = root.
While cur is not null or stack is not empty:
- If cur exists:
  - Add cur.val to res.
  - Push cur.right onto the stack.
  - Move cur to cur.left.
- Else:
  - Pop from the stack and set cur to that node.
Return res.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        stack = []
        cur = root

        while cur or stack:
            if cur:
                res.append(cur.val)
                stack.append(cur.right)
                cur = cur.left
            else:
                cur = stack.pop()

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(n)$ space for the stack.
- $O(n)$ space for the output array.

3. Morris Traversal

Intuition

Morris Traversal lets us do preorder traversal without recursion and without a stack, using O(1) extra space.

The key idea:

For every node with a left child, find its inorder predecessor (rightmost node in the left subtree).
Normally, after finishing the left subtree, we would return back to the root.
Since we have no stack, we temporarily create a thread:
predecessor.right = current
On the first time we reach a node, we record its value (because preorder = Node → Left → Right).
When we come back through the created thread, we restore the tree by removing the thread and then continue to the right child.

This modifies the tree temporarily but restores it fully at the end.

Algorithm

Initialize cur = root and an empty result list res.
While cur is not null:
- If cur.left does NOT exist:
  - Visit cur (append value to res).
  - Move to cur.right.
- Else:
  - Find the inorder predecessor prev (rightmost node in cur.left).
  - If prev.right is null:
    - This is the first time visiting cur.
    - Append cur.val to res.
    - Create a thread: prev.right = cur.
    - Move to cur.left.
  - Else:
    - Thread exists → we are returning after finishing the left subtree.
    - Remove the thread: prev.right = None.
    - Move to cur.right.
Return res.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        cur = root

        while cur:
            if not cur.left:
                res.append(cur.val)
                cur = cur.right
            else:
                prev = cur.left
                while prev.right and prev.right != cur:
                    prev = prev.right

                if not prev.right:
                    res.append(cur.val)
                    prev.right = cur
                    cur = cur.left
                else:
                    prev.right = None
                    cur = cur.right

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output array.

Common Pitfalls

Adding Node Value After Recursing on Children

Preorder requires visiting the current node before its children. Adding the value after recursive calls produces postorder traversal instead.

# Wrong: this is postorder, not preorder
preorder(node.left)
preorder(node.right)
res.append(node.val)

Pushing Left Child Before Right in Stack-Based Approach

In the iterative approach, the right child must be pushed onto the stack before the left child. Since stacks are LIFO, pushing left first causes right to be processed first.

# Wrong: processes right subtree before left
stack.append(cur.left)   # should push right first
stack.append(cur.right)