BST Traversal Algorithms

The Three Orders of Depth-First Traversal

Depth-first traversal means we go as deep as possible down one path before backtracking. The difference between the three main methods—pre-order, in-order, and post-order—lies in the order in which we "visit" a node relative to its left and right subtrees. A "visit" could mean printing the node's value, adding it to a list, or performing some other operation.

The three orders are defined by the position of the Root (the current node we are looking at) in the sequence:

1. Pre-order: Root -> Left -> Right
2. In-order: Left -> Root -> Right
3. Post-order: Left -> Right -> Root

To get a clear formal introduction to these three algorithms, please watch the beginning of the following video.

A Visual Trick for Remembering Traversals

These definitions can feel a bit abstract at first. A helpful way to visualize them is to imagine tracing a path around the outside of the tree. The order in which you pass a node for the first, second, or third time corresponds to a specific traversal.

Implementing Traversal Methods in Python

Just as we did with add_child, we can implement these traversal algorithms as methods within our BinarySearchTreeNode class. Their recursive structure is very elegant and maps directly to their definitions. For each traversal method, the logic will be:

1. Base Case: If the current node is None, there's nothing to do, so we simply return.
2. Recursive Step: Make recursive calls to traverse the left and right children, and "visit" the current node. The sequence of these three actions is what makes each traversal unique.

Let's look at the implementation for each.

1. In-order Traversal (Left -> Root -> Right)

In-order traversal is particularly special for a BST. Because it visits the left subtree, then the root, then the right subtree, it processes all the smaller values, then the current value, then all the larger values. The result? An in-order traversal of a BST visits the nodes in sorted, ascending order. This is an extremely useful property.

Let's read a short explanation to build intuition before we write the code.

Here is the implementation as a method in our class. We'll have it return a list of the visited values.

def in_order_traversal(self):
    """Performs an in-order traversal and returns a list of node values."""
    elements = []




    # 1. Visit left subtree
    if self.left:
        elements += self.left.in_order_traversal()




    # 2. Visit root node (self)
    elements.append(self.data)




    # 3. Visit right subtree
    if self.right:
        elements += self.right.in_order_traversal()

    return elements

Notice how the code directly mirrors the "Left -> Root -> Right" definition. The += operator is used here to combine the lists returned from the recursive calls.

2. Pre-order Traversal (Root -> Left -> Right)

Pre-order traversal visits the root node before exploring its children. This is useful for tasks like creating a copy of a tree, because you can create the root node first and then recursively build its subtrees.

The implementation is a simple reordering of the steps from our in-order method.

def pre_order_traversal(self):
    """Performs a pre-order traversal and returns a list of node values."""
    elements = []




    # 1. Visit root node (self)
    elements.append(self.data)




    # 2. Visit left subtree
    if self.left:
        elements += self.left.pre_order_traversal()




    # 3. Visit right subtree
    if self.right:
        elements += self.right.pre_order_traversal()

    return elements

3. Post-order Traversal (Left -> Right -> Root)

Post-order traversal visits the root node after exploring both its left and right subtrees. This is essential when you need to process a node's children before the node itself, such as when deleting nodes from a tree to free up memory. You must delete the children before you can delete the parent.

And here is its implementation:

def post_order_traversal(self):
    """Performs a post-order traversal and returns a list of node values."""
    elements = []
    



    # 1. Visit left subtree
    if self.left:
        elements += self.left.post_order_traversal()




    # 2. Visit right subtree
    if self.right:
        elements += self.right.post_order_traversal()




    # 3. Visit root node (self)
    elements.append(self.data)

    return elements

Hands-On Practice

Let's integrate these new methods into our full BinarySearchTreeNode class and test them. The following script uses the build_tree function from the last lesson to create a BST and then calls each of the three traversal methods, printing the results.

Copy this code into a file named bst_traversals.py and run it.

# bst_traversals.py

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

    def add_child(self, data):
        if data == self.data:
            return
        if data < self.data:
            if self.left:
                self.left.add_child(data)
            else:
                self.left = BinarySearchTreeNode(data)
        else:
            if self.right:
                self.right.add_child(data)
            else:
                self.right = BinarySearchTreeNode(data)

    def in_order_traversal(self):
        elements = []
        if self.left:
            elements += self.left.in_order_traversal()
        elements.append(self.data)
        if self.right:
            elements += self.right.in_order_traversal()
        return elements

    def pre_order_traversal(self):
        elements = [self.data] # Visit root first
        if self.left:
            elements += self.left.pre_order_traversal()
        if self.right:
            elements += self.right.pre_order_traversal()
        return elements

    def post_order_traversal(self):
        elements = []
        if self.left:
            elements += self.left.post_order_traversal()
        if self.right:
            elements += self.right.post_order_traversal()
        elements.append(self.data) # Visit root last
        return elements

def build_tree(elements):
    if not elements:
        return None
    
    root = BinarySearchTreeNode(elements[0])
    for i in range(1, len(elements)):
        root.add_child(elements[i])
    
    return root




# --- Main part of the script ---

numbers = [15, 12, 27, 7, 14, 20, 88, 23]
bst_root = build_tree(numbers)




# --- Test the traversals ---
print("Input list:", numbers)
print("In-order traversal:", bst_root.in_order_traversal())
print("Pre-order traversal:", bst_root.pre_order_traversal())
print("Post-order traversal:", bst_root.post_order_traversal())

Self-Check Exercise: Before you run the script, try to manually trace the pre-order traversal for the numbers list. Start with the root (15), then go left (12), left again (7), and so on. Compare your hand-traced result with the output from the script.

Time and Space Complexity

Analyzing the efficiency of these algorithms is key for interview preparation.

• Time Complexity: For all three traversals, the time complexity is $O(n)$, where $n$ is the number of nodes in the tree. This is because each traversal algorithm must visit every node in the tree exactly once.
• Space Complexity: The space complexity comes from the memory used by the recursion call stack. In the worst case (a completely unbalanced, or skewed, tree), the recursion can go $n$ levels deep. In the best and average cases (a balanced tree), the height is about $\log n$. Therefore, the space complexity is $O(h)$, where $h$ is the height of the tree. This is $O(n)$ in the worst case and $O(\log n)$ in the best/average case.

Conclusion

Excellent work today! You have successfully implemented the three fundamental depth-first traversal algorithms for a BST. These patterns are building blocks for countless other tree algorithms you will encounter.

Key Takeaways:

• Tree traversal is the process of visiting every node in a tree exactly once.
• The three main depth-first traversals are defined by the order in which they visit the Root, Left subtree, and Right subtree.
  • Pre-order: Root -> Left -> Right
  • In-order: Left -> Root -> Right
  • Post-order: Left -> Right -> Root
• In-order traversal of a BST yields the nodes' values in sorted order.
• All three traversals have a time complexity of $O(n)$ and a space complexity of $O(h)$ due to recursion.

Preview of the Next Lesson:

We've now touched on the difference in performance between balanced and unbalanced trees several times. In the next lesson, we will dive deeper into this concept. You will learn to analyze the time complexity of BST operations in balanced vs. unbalanced cases, which is a critical topic for understanding algorithm performance.