Recursive Tree Traversal: Preorder, Inorder, Postorder

1. What is Tree Traversal?

Unlike linear data structures like arrays, trees can be traversed in multiple ways. The three methods we'll learn today are all types of Depth-First Search (DFS), where we go as deep as possible down one path before backtracking.

The difference between them lies in the order in which they visit three key components at any given node:

1. The node itself (which we'll call Root for simplicity)
2. The entire left subtree
3. The entire right subtree

The order in which you perform these three actions defines the traversal type.

Let's define the three main orders:

• Preorder Traversal: Visit the Root first, then recursively traverse the Left subtree, and finally, recursively traverse the Right subtree. (Order: Root -> Left -> Right)
• Inorder Traversal: Recursively traverse the Left subtree first, then visit the Root, and finally, recursively traverse the Right subtree. (Order: Left -> Root -> Right)
• Postorder Traversal: Recursively traverse the Left subtree first, then the Right subtree, and finally, visit the Root. (Order: Left -> Right -> Root)

To see these definitions and a clear explanation of their recursive nature, the following article is an excellent reference.

2. Recursive Implementation in Python

The beauty of these traversals is that their recursive structure leads to very elegant and concise code. The core idea for each is the same:

1. Base Case: If the current node is None, we have reached the end of a path, so we do nothing and return.
2. Recursive Step: Perform the three actions (visit Root, traverse Left, traverse Right) in the specific order for the traversal type.

Let's build the code for each one. The following video provides a fantastic, step-by-step walkthrough of building a tree and implementing these traversals. We will use it as a guide.

Let's break down the implementation for each traversal. We will assume we have the Node class from the previous lesson and are writing functions that take a root node as input.

Preorder Traversal (Root -> Left -> Right)

This traversal is useful when you need to process the root before its descendants, for example, when creating a copy of a tree.

Conceptual Walkthrough:

1. Start at the root. Print its value.
2. Move to the left child. Print its value.
3. Continue down the left path, printing values, until you hit None.
4. Backtrack to the last node and go to its right child.
5. Repeat the process.

Here's a simple and common way to write it in Python, often seen in competitive programming platforms:

# Assuming the Node class is defined as in the previous lesson
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def preorder_traversal(node):
    """Performs a preorder traversal of the tree."""
    if node is None:
        return
    
    # 1. Visit the root
    print(node.val, end=' ')
    
    # 2. Traverse the left subtree
    preorder_traversal(node.left)
    
    # 3. Traverse the right subtree
    preorder_traversal(node.right)

Inorder Traversal (Left -> Root -> Right)

This traversal is famous for its application in Binary Search Trees (BSTs), as it visits the nodes in sorted order. We will explore BSTs in a later module.

Conceptual Walkthrough:

1. Start at the root, but don't print yet.
2. Go as far left as possible.
3. When you can't go left anymore, print the current node's value.
4. Move to the right child of that node and repeat the process.
5. As you backtrack up the tree, print the parent nodes' values.

The code is a simple permutation of the preorder function:

def inorder_traversal(node):
    """Performs an inorder traversal of the tree."""
    if node is None:
        return
    
    # 1. Traverse the left subtree
    inorder_traversal(node.left)
    
    # 2. Visit the root
    print(node.val, end=' ')
    
    # 3. Traverse the right subtree
    inorder_traversal(node.right)

Notice how the only thing that changed is the position of the print() statement!

Postorder Traversal (Left -> Right -> Root)

This is useful when you need to process the children before the node itself. A classic example is deleting a tree from memory, as you must delete the children before you can delete their parent.

Conceptual Walkthrough:

1. Start at the root, but don't print.
2. Go as far left as possible.
3. From there, explore the right subtree.
4. Only print a node's value after you have fully explored both its left and right subtrees.

Again, we just rearrange the operations:

def postorder_traversal(node):
    """Performs a postorder traversal of the tree."""
    if node is None:
        return
    
    # 1. Traverse the left subtree
    postorder_traversal(node.left)
    
    # 2. Traverse the right subtree
    postorder_traversal(node.right)
    
    # 3. Visit the root
    print(node.val, end=' ')

      F
     / \
    B   G
   / \   \
  A   D   I
     / \ /
    C  E H 

3. Complexity Analysis for Competitive Programming

For competitive programming, understanding the efficiency of an algorithm is just as important as knowing how to implement it.

Time Complexity

In all three recursive traversals, we visit every node in the tree exactly once. Therefore, the time complexity is directly proportional to the number of nodes, $N$.

• Time Complexity: $O(N)$

Space Complexity

The space complexity comes from the memory used by the recursion call stack. The maximum depth of the recursion is equal to the height of the tree, $H$.

• Best Case (Balanced Tree): In a well-balanced tree, the height $H$ is approximately $\log N$. So, the space complexity is $O(\log N)$.
• Worst Case (Skewed Tree): In a completely unbalanced tree (like a linked list), the height $H$ is equal to the number of nodes $N$. So, the space complexity is $O(N)$.

This is a critical trade-off to remember. While recursion is elegant, a very deep, unbalanced tree can lead to a StackOverflowError.

For a more formal look at this analysis, the following resource is very helpful.

Conclusion

In this lesson, we demystified the three fundamental recursive tree traversals. You've learned not only how to implement them but also why their structure is so powerful and how to analyze their performance.

Key Takeaways:

• Tree traversal is the process of visiting every node in a tree.
• The three main recursive DFS traversals are preorder (Root-Left-Right), inorder (Left-Root-Right), and postorder (Left-Right-Root).
• The recursive implementations are elegant and differ only in the order of three operations: visiting the root, traversing left, and traversing right.
• The time complexity for all three is $O(N)$.
• The space complexity is $O(H)$, where $H$ is the tree's height, leading to a best case of $O(\log N)$ and a worst case of $O(N)$.

Up Next:
Recursion is a natural fit for tree problems, but it's not the only way. Sometimes, an iterative approach is preferred, either to avoid recursion depth limits or for specific problem constraints. In our next lesson, we will learn how to implement an inorder traversal iteratively using a stack.