Binary Tree Traversal Algorithms

1. The "Depth-First" Approach to Traversal

When we want to visit every node in a tree, we need a strategy. The three methods we are covering today—preorder, inorder, and postorder—are all forms of Depth-First Search (DFS). As the name suggests, this strategy involves going as deep as possible down one path before backtracking and exploring other paths.

The key difference between these three traversals lies in the order in which they perform three simple actions at each node:

1. Visit the Root (e.g., read or print its value).
2. Traverse the Left Subtree.
3. Traverse the Right Subtree.

The specific sequence of these actions defines the traversal type.

To get a clear overview of this concept, let's watch a video.

2. A Closer Look at the Three Traversals

As you saw in the video, the names of the traversals give a clue about when the root node is processed relative to its children. Let's summarize:

• Preorder Traversal (Root - Left - Right)

  • Order: First, visit the current node (the "root" of the subtree). Then, recursively traverse the entire left subtree. Finally, recursively traverse the entire right subtree.
  • Use Case: Useful for creating a copy of a tree or getting a prefix expression from an expression tree. The root is processed first, so you can create the parent node before attaching its children.

• Inorder Traversal (Left - Root - Right)

  • Order: First, recursively traverse the entire left subtree. Then, visit the current node. Finally, recursively traverse the entire right subtree.
  • Use Case: As we saw in the previous lesson, this traversal visits the nodes of a Binary Search Tree in sorted (ascending) order, which is great for validation or data retrieval.

• Postorder Traversal (Left - Right - Root)

  • Order: First, recursively traverse the entire left subtree. Then, recursively traverse the entire right subtree. Finally, visit the current node.
  • Use Case: Useful when you need to process a node's children before the node itself. A classic example is deleting a tree; you must delete the children before you can delete the parent to avoid creating orphaned nodes.

This image provides a great visual summary of the three traversals on an example tree.

3. Implementing Traversal Algorithms in Python

Now let's translate these concepts into code. Recursion is a very natural way to implement these algorithms, as the definition of each traversal is itself recursive ("traverse the subtree").

The following article provides excellent, well-explained Python implementations for each traversal type.

Putting It All Together

Let's integrate these three new traversal methods into the BinarySearchTreeNode class we built in the previous lesson. Notice how similar the code is for each method—the only thing that changes is the position of the print() statement (or whatever action you're taking on the node).

class BinarySearchTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    # --- Insertion and Search from previous lesson ---
    def insert(self, data):
        if self.data == data:
            return 
        if data < self.data:
            if self.left:
                self.left.insert(data)
            else:
                self.left = BinarySearchTreeNode(data)
        else:
            if self.right:
                self.right.insert(data)
            else:
                self.right = BinarySearchTreeNode(data)

    # --- Traversal Methods ---

    def inorder_traversal(self):
        """Returns a list of elements in Left-Root-Right order."""
        elements = []
        # 1. Visit left subtree
        if self.left:
            elements += self.left.inorder_traversal()
        
        # 2. Visit base node
        elements.append(self.data)
        
        # 3. Visit right subtree
        if self.right:
            elements += self.right.inorder_traversal()
            
        return elements

    def preorder_traversal(self):
        """Returns a list of elements in Root-Left-Right order."""
        elements = []
        # 1. Visit base node
        elements.append(self.data)

        # 2. Visit left subtree
        if self.left:
            elements += self.left.preorder_traversal()
        
        # 3. Visit right subtree
        if self.right:
            elements += self.right.preorder_traversal()
            
        return elements
        
    def postorder_traversal(self):
        """Returns a list of elements in Left-Right-Root order."""
        elements = []
        # 1. Visit left subtree
        if self.left:
            elements += self.left.postorder_traversal()
        
        # 2. Visit right subtree
        if self.right:
            elements += self.right.postorder_traversal()
            
        # 3. Visit base node
        elements.append(self.data)
        
        return elements

# Helper function to build a tree
def build_tree(elements):
    if not elements:
        return None
    root = BinarySearchTreeNode(elements[0])
    for i in range(1, len(elements)):
        root.insert(elements[i])
    return root

# --- Let's test it out! ---
numbers = [15, 12, 7, 14, 27, 20, 88]
number_tree = build_tree(numbers)

print("Original elements:", numbers)
print("--------------------------------")
print("Inorder (Left-Root-Right):  ", number_tree.inorder_traversal())
print("Preorder (Root-Left-Right): ", number_tree.preorder_traversal())
print("Postorder (Left-Right-Root):", number_tree.postorder_traversal())

Expected Output:

Original elements: [15, 12, 7, 14, 27, 20, 88]
--------------------------------
Inorder (Left-Root-Right):   [7, 12, 14, 15, 20, 27, 88]
Preorder (Root-Left-Right):  [15, 12, 7, 14, 27, 20, 88]
Postorder (Left-Right-Root): [7, 14, 12, 20, 88, 27, 15]

      15
     /  \
    12   27
   / \   / \
  7  14 20  88

Conclusion

Great work! You have now mastered the three fundamental depth-first traversal algorithms for binary trees. These patterns are essential building blocks for more complex tree-based algorithms you will encounter in your studies for the GATE exam.

Key Takeaways:

• Tree traversal is the process of visiting every node in a tree exactly once.
• Preorder, Inorder, and Postorder are all depth-first traversal strategies.
• The difference lies in when the root node is visited relative to its left and right subtrees:
  • Preorder: Root -> Left -> Right
  • Inorder: Left -> Root -> Right
  • Postorder: Left -> Right -> Root
• Recursion provides an elegant and intuitive way to implement these traversals, as their definitions are naturally recursive.

Preview of the Next Lesson:

We've spent the last few lessons on tree structures. Now, we are going to switch gears to another incredibly powerful and widely used data structure. In the next lesson, you will implement a hash table using separate chaining for collision resolution. You'll discover how hash tables can provide average-case constant time—$O(1)$—performance for insertions, deletions, and lookups, making them a cornerstone of modern software.