Preorder Traversal in Binary Trees

Understanding Preorder Traversal

"Traversal means visiting every node in a tree exactly once."

What is Preorder Traversal? Preorder traversal follows the order:

1. Visit the root node.
2. Visit the left subtree.
3. Visit the right subtree.

This order ensures that the root is processed first, making it easy to remember as Root → Left → Right.

For example, consider the following binary tree:

                             3
                            / \
                           4   5
                          / \   \
                         6   7   8
                        

In preorder traversal, the nodes will be visited in the following order: 3, 4, 6, 7, 5, 8.

Python Implementation: Recursive Approach

Here’s a Python code snippet to perform preorder traversal using recursion:

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

# Function to perform preorder traversal
def preorder_traversal(root):
    if not root:  # Base case: If the node is None, return
        return
    print(root.value, end=" ")  # Process the root node
    preorder_traversal(root.left)  # Traverse the left subtree
    preorder_traversal(root.right)  # Traverse the right subtree

# Example Usage
if __name__ == "__main__":
    # Creating the binary tree from the example
    root = TreeNode(3)
    root.left = TreeNode(6)
    root.right = TreeNode(9)
    root.left.left = TreeNode(12)
    root.left.right = TreeNode(5)
    root.right.left = TreeNode(3)
    root.right.right = TreeNode(4)

    print("Preorder Traversal:")
    preorder_traversal(root)

In the recursive function above, we check if the current node exists. If it does, we visit the root node, traverse the left subtree, and then the right subtree.

Preorder Traversal: Iterative Approach

An iterative approach uses a stack to mimic recursion. This method can be more space-efficient in environments with limited recursion depth.

def iterative_preorder_traversal(root):
    if not root:
        return
    stack = [root]
    while stack:
        current = stack.pop()
        print(current.value, end=" ")
        if current.right:  # Push right child first
            stack.append(current.right)
        if current.left:  # Push left child
            stack.append(current.left)

# Example Usage
print("\nIterative Preorder Traversal:")
iterative_preorder_traversal(root)

In the recursive function above, we check if the current node exists. If it does, we visit the root node, traverse the left subtree, and then the right subtree.

Practical Implementation

Here’s how you can call the function to perform preorder traversal on a binary tree:

# Example binary tree node class
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Building the binary tree
root = Node(3)
root.left = Node(4)
root.right = Node(5)
root.left.left = Node(6)
root.left.right = Node(7)
root.right.right = Node(8)

# Perform preorder traversal
print("Preorder Traversal Result:")
preorder_traversal(root)
                        

The output of the above code will be: 3, 4, 6, 7, 5, 8.