LeetCode 144: Binary Tree Preorder Traversal

Problem Restatement

We are given the root of a binary tree.

Return the preorder traversal of its node values.

Preorder traversal visits nodes in this order:

root -> left subtree -> right subtree

The tree may be empty. In that case, return an empty list. LeetCode also includes a follow-up asking for an iterative solution.

Examples

Example 1:

    1
     \
      2
     /
    3

Preorder traversal:

visit 1
go right to 2
visit 2
go left to 3
visit 3

Output:

[1, 2, 3]

Example 2:

root = []

Output:

[]

Example 3:

root = [1]

Output:

[1]

Input and Output

Item	Meaning
Input	root: Optional[TreeNode]
Output	list[int]
Traversal order	Root, left subtree, right subtree
Empty tree	Return []

Function shape:

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        ...

Core Idea

Preorder traversal is a depth-first traversal.

At each node, we do three things:

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

So the recursive structure follows the traversal definition directly:

visit(node)
preorder(node.left)
preorder(node.right)

Recursive Algorithm

Create an empty result list.

Define a helper function:

dfs(node)

For each node:

1. If node is None, return.
2. Append node.val to the result.
3. Recursively traverse node.left.
4. Recursively traverse node.right.

Return the result list.

Correctness

For any non-empty subtree, preorder traversal requires visiting the subtree root before its children.

The algorithm first appends the current node value, so it visits the root first.

Then it recursively applies the same rule to the left subtree, which returns all left-subtree values in preorder.

After that, it recursively applies the same rule to the right subtree, which returns all right-subtree values in preorder.

Therefore, every subtree is processed in root-left-right order. Applying this to the original root gives the preorder traversal of the whole tree.

If the tree is empty, the helper does nothing and the result remains empty, so the algorithm returns [].

Complexity

Let n be the number of nodes and h be the height of the tree.

Metric	Value	Why
Time	O(n)	Each node is visited once
Space	O(h)	Recursion stack follows one root-to-leaf path

In the worst case, a skewed tree has height n.

Recursive Implementation

from typing import Optional

# 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]:
        result = []

        def dfs(node: Optional[TreeNode]) -> None:
            if node is None:
                return

            result.append(node.val)
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return result

Code Explanation

The result list stores visited values:

result = []

The helper receives the current node:

def dfs(node: Optional[TreeNode]) -> None:

The base case stops at missing children:

if node is None:
    return

Preorder visits the root first:

result.append(node.val)

Then it visits the left subtree:

dfs(node.left)

Then it visits the right subtree:

dfs(node.right)

Finally, the main function returns the collected values:

return result

Iterative Implementation

The follow-up asks for an iterative solution.

Use a stack.

Because a stack is last-in-first-out, push the right child before the left child. That way, the left child is processed first.

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        if root is None:
            return []

        result = []
        stack = [root]

        while stack:
            node = stack.pop()
            result.append(node.val)

            if node.right is not None:
                stack.append(node.right)

            if node.left is not None:
                stack.append(node.left)

        return result

Iterative Code Explanation

Start with the root on the stack:

stack = [root]

While there is a node to process:

node = stack.pop()

visit it:

result.append(node.val)

Push the right child first:

if node.right is not None:
    stack.append(node.right)

Then push the left child:

if node.left is not None:
    stack.append(node.left)

Since the left child is on top of the stack, it is processed before the right child.

Testing

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

def run_tests():
    s = Solution()

    root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
    assert s.preorderTraversal(root) == [1, 2, 3]

    assert s.preorderTraversal(None) == []

    root = TreeNode(1)
    assert s.preorderTraversal(root) == [1]

    root = TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3),
    )
    assert s.preorderTraversal(root) == [1, 2, 4, 5, 3]

    root = TreeNode(1, TreeNode(2, TreeNode(3)))
    assert s.preorderTraversal(root) == [1, 2, 3]

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
1 -> right 2 -> left 3	Standard LeetCode example shape
Empty tree	Returns empty list
Single node	Root-only traversal
Full mixed tree	Confirms root-left-right order
Left-skewed tree	Confirms recursive descent order