Pre-Order Traversal

Pre-Order Traversal

In the previous tutorial, we learned about the general structure of Binary Trees and the three main types of traversals.

Now, we will take a deep dive into Pre-Order Traversal.

This is an incredibly important algorithm for technical interviews and has very specific real-world use cases.

1. What is Pre-Order Traversal?

Tree traversal means visiting every single node in the tree exactly one time.

Because trees are not linear like arrays, we cannot just loop from index 0 to the end. We need a specific path to follow.

Pre-Order Traversal follows a very strict path:

1. Root: First, visit the current node (the Root of the subtree).
2. Left: Second, recursively visit the entire Left subtree.
3. Right: Third, recursively visit the entire Right subtree.

The prefix "Pre" means "Before". This helps you remember that we visit the Root before we visit its children!

Pre-Order Traversal: Notice how the numbering follows the Root -> Left -> Right pattern.

2. A Step-by-Step Example

Let's look at the tree in the diagram above and trace the execution path.

The nodes are lettered A through G.

Step 1:

• Start at the absolute Root of the tree: Node A.
• Rule 1 says visit the Root. We print A.
• Rule 2 says go Left.

Step 2:

• We are now at Node B.
• Rule 1 says visit the Root. We print B.
• Rule 2 says go Left.

Step 3:

• We are now at Node C.
• Rule 1 says visit the Root. We print C.
• Rule 2 says go Left. There is no left child!
• Rule 3 says go Right. There is no right child!
• Node C is fully processed. We move back up to B.

Step 4:

• Node B has already done Rule 1 (visited itself) and Rule 2 (visited Left).
• Now it does Rule 3: go Right.
• We are now at Node D.
• Rule 1 says visit the Root. We print D.
• No left or right children exist. Node D is processed.
• Node B is fully processed. We move back up to A.

Step 5:

• Node A has already done Rule 1 and Rule 2.
• Now it does Rule 3: go Right.
• We are now at Node E.
• Rule 1 says visit the Root. We print E.
• Rule 2 says go Left.

Step 6:

• We are now at Node F.
• Rule 1 says visit the Root. We print F.
• No children exist. Move back up to E.

Step 7:

• Node E does Rule 3: go Right.
• We are now at Node G.
• Rule 1 says visit the Root. We print G.

Final Output: A, B, C, D, E, F, G

3. Why Use Pre-Order Traversal?

Every traversal has a superpower. What is Pre-Order good for?

1. Copying / Cloning a Tree If you want to create an exact duplicate of a tree, you need to know the Root first! Because Pre-Order visits the Root before the children, it is the perfect algorithm for generating a perfect clone of a tree structure.

2. Prefix Notation (Polish Notation) In mathematical expression trees, Pre-Order traversal is used to generate Prefix Expressions (like + * A B C). This is highly useful for compilers and calculators.

3. Flattening a Tree If you need to flatten a hierarchical tree into a linear Linked List, Pre-Order is often the requested ordering in technical interviews.

4. Code Example (Python)

Let's write the code for Pre-Order Traversal.

Notice how elegant and short the code is. This is the power of Recursion!

# 1. Create the Node Class
class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

# 2. Define the Pre-Order function
def preorder_traversal(node):
    # Base case: If the node is None, stop!
    if node is not None:
        # 1. Visit the Root (Print it)
        print(node.data, end=" ")
        # 2. Traverse the Left Subtree
        preorder_traversal(node.left)
        # 3. Traverse the Right Subtree
        preorder_traversal(node.right)
# 3. Build the Tree
root = Node("A")
root.left = Node("B")
root.right = Node("E")
root.left.left = Node("C")
root.left.right = Node("D")
root.right.left = Node("F")
root.right.right = Node("G")
# 4. Run the Algorithm
print("Pre-Order Output:")
preorder_traversal(root)

5. Time and Space Complexity

• Time Complexity: O(n). Every single node in the tree is visited exactly once. Therefore, the time it takes scales linearly with the number of nodes (n).
• Space Complexity: O(h). Where h is the maximum height of the tree. This space is used by the Call Stack during recursion. In a perfectly balanced tree, the height is log n, making it O(log n) space. In a heavily unbalanced tree (like a linked list), it could be O(n) space.