Tree Traversal: Pre-order, In-order, and Post-order

1. Depth-First Traversal: The Core Idea

While level-order (BFS) explores nodes layer by layer, Depth-First Search (DFS) dives as deep as possible down one path before backtracking and exploring other paths. For a binary tree, this involves a recursive strategy centered on three key actions for any given node:

1. "Visit" the current node (e.g., read or print its value).
2. Recursively traverse its left subtree.
3. Recursively traverse its right subtree.

The three main DFS traversals—pre-order, in-order, and post-order—are defined simply by the order in which these three actions are performed.

Let's start by understanding this classification. The following short video provides an excellent explanation of what "pre-", "in-", and "post-" signify in the context of tree traversal.

To summarize the rules:

• Pre-order: [Root] -> [Left Subtree] -> [Right Subtree]
• In-order: [Left Subtree] -> [Root] -> [Right Subtree]
• Post-order: [Left Subtree] -> [Right Subtree] -> [Root]

The image below provides a great visual summary of these rules and shows the resulting traversals for an example tree.

2. The Power of Recursion

Because a binary tree is a recursive data structure (every node is the root of its own smaller subtree), recursion is the most natural and elegant way to implement these traversals. The function's logic at any node is the same: apply the traversal rule (e.g., Root-Left-Right) and call itself on its children.

The magic that makes this work is the call stack. As your program makes recursive calls, the stack keeps track of where you are in the traversal, what you've already done, and what you still need to do.

To see this in action, we'll do a deep dive into a pre-order traversal. The following video masterfully illustrates how the recursive calls are pushed onto and popped from the call stack. Understanding this mechanism is key to truly grasping recursion.

3. Implementing the Three Traversals

As you saw in the video, the recursive implementation is surprisingly concise. The code for all three traversals is nearly identical; only the sequence of the three core actions changes.

Let's look at the implementation in Python. The following resource provides clean code examples for a basic Node class and each of the three recursive traversal functions.

Here's the essence of the Python implementation you just reviewed for a Node class with val, left, and right attributes:

Pre-order (Root -> Left -> Right)

def preorderTraversal(root):
    if not root:
        return
    print(root.val)             # Visit Root
    preorderTraversal(root.left)  # Recurse Left
    preorderTraversal(root.right) # Recurse Right

In-order (Left -> Root -> Right)

def inorderTraversal(root):
    if not root:
        return
    inorderTraversal(root.left)   # Recurse Left
    print(root.val)             # Visit Root
    inorderTraversal(root.right)  # Recurse Right

Post-order (Left -> Right -> Root)

def postorderTraversal(root):
    if not root:
        return
    postorderTraversal(root.left)   # Recurse Left
    postorderTraversal(root.right)  # Recurse Right
    print(root.val)               # Visit Root

The base case if not root: return is crucial. It stops the recursion when we try to traverse a non-existent child (i.e., a None pointer), which happens when we reach a leaf node's children.

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

4. Complexity Analysis

Understanding the performance is vital for interviews. For all three recursive DFS traversals:

• Time Complexity: O(N)
  Each node is visited exactly once. The work done at each node (a print statement and two recursive calls) is constant time, O(1). Therefore, the total time complexity is linear in the number of nodes, N.

• Space Complexity: O(H)
  While we aren't using any extra data structures like a queue, the recursive calls consume space on the call stack. The maximum depth of the call stack will be equal to the height (H) of the tree.

  • Worst Case (Skewed Tree): If the tree is essentially a linked list, its height H is N. The space complexity becomes O(N).
  • Best/Average Case (Balanced Tree): For a reasonably balanced tree, the height H is approximately log(N). The space complexity is O(log N).

Conclusion

Great job! You've now covered the fundamental recursive patterns for traversing a binary tree using DFS. These three traversals—pre-order, in-order, and post-order—are the foundation for solving countless problems involving tree manipulation, path finding, and structural analysis.

Key Takeaways:

• DFS traversals explore as deep as possible before backtracking.
• The three main types are defined by when the root is visited relative to its left and right subtrees.
  • Pre-order: Root, Left, Right
  • In-order: Left, Root, Right
  • Post-order: Left, Right, Root
• Recursion provides an elegant and concise implementation for these traversals, leveraging the call stack for state management.
• The time complexity is O(N) for all three, and the space complexity is O(H) due to the recursion depth.

In the next lesson, we will tackle a common interview follow-up: implementing these same traversals iteratively using an explicit stack. This will test your understanding of stack mechanics and give you an even deeper appreciation for how these traversals work under the hood.