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

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.

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: