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:

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

    print(node.data, end=' ')

    preorder_traversal(node.left)

    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__':

    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)


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)

result = preorder_to_list(root)
print(result)

Output:

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

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

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).

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

Time and Space Complexity

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.

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.