Binary Tree Traversal Methods

Hello! In our last session, we successfully built the mechanisms to insert data into a Binary Search Tree and to search for specific values. You saw how the recursive nature of the BST's definition translates directly into elegant C code.

Now that we can populate a tree, a new question arises: how do we visit and process every single node in a systematic way? This is crucial for tasks like printing all values, calculating their sum, or even deallocating the tree's memory.

Today, you will learn to implement in-order, pre-order, and post-order traversals for a binary tree. These three powerful, recursive algorithms form the bedrock of many tree-based operations. They are all forms of "depth-first" traversal, where we go as deep as possible down one path before exploring others.

1. The Three Flavors of Depth-First Traversal

Every traversal algorithm for a binary tree must perform three fundamental actions for any given node:

1. Visit the Root node (e.g., print its data).
2. Traverse the entire Left subtree.
3. Traverse the entire Right subtree.

The difference between in-order, pre-order, and post-order is simply the sequence in which these three actions are performed. The logic is inherently recursive: when we "traverse a subtree," we apply the exact same traversal logic to the root of that subtree.

The three orderings are:

• Pre-order Traversal: Root -> Left -> Right

  • Visit the current node first.
  • Then, recursively traverse the left subtree.
  • Finally, recursively traverse the right subtree.
  • Use case: Creating a copy of the tree.

• In-order Traversal: Left -> Root -> Right

  • Recursively traverse the left subtree first.
  • Then, visit the current node.
  • Finally, recursively traverse the right subtree.
  • Special Property: For a BST, this traversal visits nodes in ascending sorted order.

• Post-order Traversal: Left -> Right -> Root

  • Recursively traverse the left subtree first.
  • Then, recursively traverse the right subtree.
  • Finally, visit the current node.
  • Use case: Deleting the tree, as you can delete children before their parent.

To make this concrete, study the following image. It shows the path a traversal takes (dashed line) and uses colored dots to mark the moment a node is "visited" for each of the three traversal types.

2. Recursive Implementation and Execution Flow

The recursive definitions of these traversals lead to very concise C functions. The base case for the recursion is always an empty tree (i.e., when the node pointer is NULL).

The following video provides an exceptionally clear explanation of these concepts. It starts by defining the traversals and then does a detailed walkthrough of implementing and tracing a pre-order traversal, which will solidify your understanding of the recursive call stack.

3. C Code for Traversal Functions

As you saw in the video, the C code for these functions is surprisingly simple. Each function takes a pointer to a node as its argument.

// In-order traversal: Left -> Root -> Right
void inorderTraversal(struct node* root) {
    if (root == NULL) return; // Base case

    inorderTraversal(root->left);    // 1. Visit left subtree
    printf("%d -> ", root->item);    // 2. Visit root
    inorderTraversal(root->right);   // 3. Visit right subtree
}

// Pre-order traversal: Root -> Left -> Right
void preorderTraversal(struct node* root) {
    if (root == NULL) return; // Base case

    printf("%d -> ", root->item);    // 1. Visit root
    preorderTraversal(root->left);   // 2. Visit left subtree
    preorderTraversal(root->right);  // 3. Visit right subtree
}

// Post-order traversal: Left -> Right -> Root
void postorderTraversal(struct node* root) {
    if (root == NULL) return; // Base case

    postorderTraversal(root->left);  // 1. Visit left subtree
    postorderTraversal(root->right); // 2. Visit right subtree
    printf("%d -> ", root->item);    // 3. Visit root
}

This animated GIF provides another way to visualize the post-order traversal (Left -> Right -> Root) process.

4. Practice: Adding Traversal to Your BST Program

Now, let's integrate these new functions into the program from our last lesson. This will give you hands-on experience and allow you to see the output for yourself.

Your Task:

1. Take the complete C program from the previous lesson (the one with the insert and search functions).
2. Copy and paste the three new traversal functions (inorderTraversal, preorderTraversal, postorderTraversal) into your file. Make sure your node struct member is named data (or change root->item to root->data in the traversal functions to match).
3. In your main function, after you finish inserting all the nodes, add the following lines to call each traversal function:

// ... after all the insert calls ...

printf("In-order traversal:\n");
inorderTraversal(root);
printf("\n\n");

printf("Pre-order traversal:\n");
preorderTraversal(root);
printf("\n\n");

printf("Post-order traversal:\n");
postorderTraversal(root);
printf("\n");

4. Before you run the code, look at the tree you built in main from the last lesson:
   50, 30, 20, 40, 70, 60, 80
   Try to trace the traversals on paper and predict the output for each of the three calls.
5. Compile and run the program. Compare the actual output with your prediction. Does the in-order traversal produce a sorted list?

For reference, here is a complete example from Programiz that ties everything together.

5. Time and Space Complexity

A brief note on efficiency, as discussed in the mycodeschool video:

• Time Complexity: All three traversal algorithms have a time complexity of $O(n)$, where $n$ is the number of nodes in the tree. This is because we must visit every node exactly once.
• Space Complexity: The space complexity is determined by the maximum depth of the recursive call stack. This is equal to the height of the tree, $h$. Therefore, the space complexity is $O(h)$.
  • In a well-balanced tree, $h\approx \log n$, so the space complexity is $O(\log n)$.
  • In the worst case (a skewed tree, essentially a linked list), $h\approx n$, leading to a space complexity of $O(n)$.

Conclusion

In this lesson, you've mastered the three fundamental depth-first traversal algorithms for binary trees. These patterns are essential building blocks for more complex tree manipulations.

Key Takeaways:

• Tree traversal is the process of visiting every node in a tree.
• Pre-order, in-order, and post-order traversals are defined by the sequence in which they visit a node (Root) relative to its Left and Right subtrees.
• Recursion is the most natural and elegant way to implement these traversals, with the base case being an empty tree (NULL pointer).
• For a Binary Search Tree, in-order traversal has the special property of visiting nodes in sorted order.

Preview of the Next Lesson:
We've spent a lot of time on trees, a powerful way to structure data. Next, we'll explore a completely different and extremely popular data structure: the hash table. You'll learn about hashing, how hash functions work, how to handle "collisions," and why hash tables offer incredibly fast average-case performance for lookups, insertions, and deletions.