How to Implement Preorder Traversal of a Binary Tree in Python

Preorder traversal is one of the three fundamental depth-first traversal techniques for binary trees. It follows the Root → Left → Right pattern: the current node is processed first, then the left subtree is traversed, and finally the right subtree is traversed.

This traversal order is particularly useful for creating a copy of a tree, serializing/deserializing tree structures, generating prefix expressions from expression trees, and exploring nodes in the order they were originally inserted.

In this guide, you will learn how preorder traversal works step by step, implement it recursively in Python, and understand its time and space complexity.

How Preorder Traversal Works

The traversal follows three rules applied recursively at every node:

1. Visit the current node (process its data; for example, print it).
2. Traverse the left subtree (recursively apply preorder traversal).
3. Traverse the right subtree (recursively apply preorder traversal).

The key distinction from other traversals is that the root is visited first, which means before either subtree is explored.

Step-by-Step Walkthrough

Consider the following binary tree:

        1
       / \
      2   3
     / \   \
    4   5   6

Here is how preorder traversal processes each node:

Step	Action	Explanation
1	Visit 1	Process the root node first
2	Go left → Visit 2	Process node 2 (root of left subtree)
3	Go left → Visit 4	Process node 4 (leaf node without children)
4	Back to 2, go right → Visit 5	Process node 5 (leaf node without children)
5	Back to 1, go right → Visit 3	Process node 3 (root of right subtree)
6	3 has no left child, go right → Visit 6	Process node 6 (leaf node without children)

Traversal result: 1 → 2 → 4 → 5 → 3 → 6

The Algorithm

The recursive algorithm is straightforward:

Preorder(node):
    1. If node is None, return (base case)
    2. Process node               (visit current node)
    3. Preorder(node.left)        (traverse left subtree)
    4. Preorder(node.right)       (traverse right subtree)

The base case (node is None) stops the recursion when we reach a leaf node's non-existent child.

Python Implementation

Defining the Node Class

Each node stores a data value and references to its left and right children:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

Implementing the Preorder Traversal Function

def preorder_traversal(node):
    """Recursively perform preorder traversal: Root → Left → Right."""
    if node is None:
        return

    # Step 1: Visit the current node
    print(node.data, end=' ')

    # Step 2: Traverse the left subtree
    preorder_traversal(node.left)

    # Step 3: Traverse the right subtree
    preorder_traversal(node.right)

Complete Example

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def preorder_traversal(node):
    """Recursively perform preorder traversal: Root → Left → Right."""
    if node is None:
        return

    print(node.data, end=' ')
    preorder_traversal(node.left)
    preorder_traversal(node.right)


if __name__ == '__main__':
    # Build the tree:
    #         1
    #        / \
    #       2   3
    #      / \   \
    #     4   5   6

    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.right = Node(6)

    print("Preorder traversal of binary tree:")
    preorder_traversal(root)

Output:

Preorder traversal of binary tree:
1 2 4 5 3 6

Returning the Traversal as a List

In practice, you often need the traversal result as a list rather than printed output:

def preorder_to_list(node):
    """Return the preorder traversal as a list of values."""
    if node is None:
        return []

    return [node.data] + preorder_to_list(node.left) + preorder_to_list(node.right)

# Build the tree:
#         1
#        / \
#       2   3
#      / \   \
#     4   5   6

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)

# We call the preorder_to_list function
result = preorder_to_list(root)
# Then search inside for results
print(result)

Output:

[1, 2, 4, 5, 3, 6]

More efficient list-building approach

The concatenation approach above creates many intermediate lists. For better performance on large trees, use an accumulator:

def preorder_to_list(node):
    """Efficiently collect preorder traversal into a list."""
    result = []

    def _traverse(n):
        if n is None:
            return
        result.append(n.data)
        _traverse(n.left)
        _traverse(n.right)

    _traverse(node)
    return result

This avoids creating and merging intermediate lists, reducing overhead from O(n²) to O(n).

More Examples

Example 1: Three-Node Tree

    A
   / \
  B   C

root = Node('A')
root.left = Node('B')
root.right = Node('C')

preorder_traversal(root)

Output:

A B C

Example 2: Left-Skewed Tree

    A
   /
  B
 /
D

root = Node('A')
root.left = Node('B')
root.left.left = Node('D')

preorder_traversal(root)

Output:

A B D

Example 3: Five-Node Tree

        A
       / \
      B   C
     / \
    D   E

root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')

preorder_traversal(root)

Output:

A B D E C

Example 4: Empty Tree

# Call with None
preorder_traversal(None)

An empty tree (root is None) produces no output because the base case returns immediately.

Why Preorder Traversal Matters

Preorder traversal is the natural choice when you need to process a parent before its children:

• Tree serialization: Save a tree's structure to a file or string. Preorder captures the root first, making reconstruction straightforward.
• Copying a tree: Create nodes in the same order as the original, starting with the parent before its children.
• Prefix expression: Convert an expression tree to Polish notation (for example, + * 2 3 4).
• Directory listing: Print a folder before its contents (like the tree command).

# Example: Create a deep copy of a tree using preorder
def copy_tree(node):
    if node is None:
        return None

    new_node = Node(node.data)              # Process root first
    new_node.left = copy_tree(node.left)    # Then left subtree
    new_node.right = copy_tree(node.right)  # Then right subtree
    return new_node

Comparison with other traversals

Traversal	Order	Common Use Cases
Preorder	Root → Left → Right	Tree copying, serialization, prefix expressions
Inorder	Left → Root → Right	Sorted output from BST, expression evaluation
Postorder	Left → Right → Root	Tree deletion, postfix expressions, dependency resolution

Time and Space Complexity

Aspect	Complexity	Explanation
Time	O(n)	Every node is visited exactly once, where n is the total number of nodes
Space (best case)	O(log n)	For a balanced tree, the recursion depth equals the tree height
Space (worst case)	O(n)	For a completely skewed tree (essentially a linked list), the recursion depth equals n

The space complexity comes from the call stack used by the recursive function. Each recursive call adds a frame to the stack, and the maximum depth equals the height of the tree.

Watch out for stack overflow on deep trees

For very deep or skewed trees (for example, with 10,000+ nodes in a chain), Python's default recursion limit (usually 1,000) will cause a RecursionError. You can increase the limit with sys.setrecursionlimit(), but for very deep trees, consider using an iterative preorder traversal with an explicit stack:

def preorder_iterative(root):
    """Iterative preorder traversal using an explicit stack."""
    if root is None:
        return []

    result = []
    stack = [root]

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

        # Push right first so left is processed first (LIFO)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

Conclusion

Preorder traversal is a fundamental binary tree algorithm that visits nodes in the Root → Left → Right order. Its recursive implementation in Python is concise, comprising only three lines of logic, and runs in O(n) time with O(h) space, where h is the tree's height.

The traversal is essential for operations where the parent must be processed before its children, such as tree copying, serialization, and prefix expression generation.

For practical applications, prefer the accumulator-based approach when collecting results into a list, and consider iterative alternatives for very deep trees to avoid hitting Python's recursion limit.