Binary Search Trees - Traversal

Tree Traversal

Traversal means visiting every node in the tree. There are three main ways to do it, each with different uses.

Three Traversal Methods

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

The names tell you when you visit the root.

In-Order Traversal

Visit left subtree, then root, then right subtree. For a BST, this gives you values in sorted order.

Implementation

For the example tree, in-order gives: 20, 30, 40, 50, 60, 70, 80. Sorted!

Pre-Order Traversal

Visit root first, then left, then right. Useful for copying trees or getting prefix expressions.

Post-Order Traversal

Visit left, then right, then root. Useful for deleting trees or getting postfix expressions.

Comparison

Iterative Traversal

You can also do traversals with a stack instead of recursion:

Level-Order Traversal

There’s also level-order (breadth-first), which visits nodes level by level:

When to Use Each

• In-order: When you need sorted values
• Pre-order: When copying or serializing
• Post-order: When deleting or calculating
• Level-order: When you need breadth-first search

Time Complexity

All traversals visit every node once:

• Time: O(n) where n is number of nodes
• Space: O(h) where h is height (O(log n) average, O(n) worst)

What’s Next?

You’ve learned all the main BST operations. Let’s test your knowledge with a quiz and some practice problems.