In-Order Traversal for Sorted BST Elements

The "Left, Node, Right" Rule and Its Magic

First, let's formally define in-order traversal. It's a type of Depth-First Search (DFS) that follows a simple, recursive rule for any given node:

1. Traverse the left subtree.
2. Visit the node itself (e.g., print its value or add it to a list).
3. Traverse the right subtree.

This is often remembered by the mnemonic LNR.

Now, recall the core property of a Binary Search Tree: for any node, all values in its left subtree are smaller, and all values in its right subtree are larger. When you combine the LNR traversal rule with this BST property, a remarkable outcome occurs: the nodes are visited in sorted, ascending order.

• By recursively going to the leftmost descendant first, you guarantee you visit the smallest value.
• After visiting all smaller values in the left subtree, you visit the current node.
• Finally, you visit all the larger values in the right subtree.

This process ensures a naturally sorted output.

To see a clear walkthrough and contrast in-order with pre-order and post-order traversals, the following video provides an excellent explanation.

1. The Recursive Implementation

Because the definition of in-order traversal is inherently recursive, implementing it with a recursive function is the most direct and intuitive approach. The function's logic directly mirrors the LNR rule.

Let's study a concise guide that explains the algorithm and presents a clean Python implementation.

Here is a typical implementation you might write in a competitive programming context. It uses a helper function to pass the result list by reference.

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorderTraversal_recursive(root: TreeNode) -> list[int]:
    result = []

    def traverse(node):
        # Base case: do nothing if the node is null
        if not node:
            return
        
        # 1. Traverse the left subtree
        traverse(node.left)
        
        # 2. Visit the node
        result.append(node.val)
        
        # 3. Traverse the right subtree
        traverse(node.right)

    traverse(root)
    return result

# Example usage with a BST:
#       4
#      / \
#     2   6
#    / \ / \
#   1  3 5  7
root = TreeNode(4, 
              TreeNode(2, TreeNode(1), TreeNode(3)), 
              TreeNode(6, TreeNode(5), TreeNode(7)))

print(inorderTraversal_recursive(root))
# Output: [1, 2, 3, 4, 5, 6, 7]

2. The Iterative Implementation

While recursion is intuitive, it has drawbacks. In competitive programming, a very deep tree can cause a "RecursionError" (stack overflow). An iterative solution using an explicit stack avoids this and is often a required skill in technical interviews.

The goal is to simulate the recursive call stack manually. The core idea is:

1. Keep pushing left children onto a stack until you can't go left anymore. The node at the top of the stack is the next one to be visited.
2. Pop a node from the stack, process its value.
3. Move to its right child and repeat the process.

This might seem tricky at first, but it perfectly mimics what the computer does during recursion. The following video provides one of the best explanations available for this process.

Here is a clean iterative implementation, similar to what you saw in the video and resources.

def inorderTraversal_iterative(root: TreeNode) -> list[int]:
    result = []
    stack = []
    current = root

    # Loop as long as there are nodes to process or nodes on the stack
    while current or stack:
        # 1. Go to the leftmost node
        while current:
            stack.append(current)
            current = current.left
        
        # At this point, `current` is None. Pop the last-seen node.
        # This is the next node to be visited in the in-order sequence.
        current = stack.pop()
        
        # 2. Visit the node
        result.append(current.val)
        
        # 3. Move to the right subtree to repeat the process
        current = current.right

    return result

print(inorderTraversal_iterative(root))
# Output: [1, 2, 3, 4, 5, 6, 7]

This pattern is extremely useful and can be adapted for pre-order and post-order iterative traversals as well. Mastering it is a significant step in your competitive programming preparation.

Complexity and Final Notes

• Time Complexity: O(N), where N is the number of nodes. Both recursive and iterative approaches visit each node exactly once.
• Space Complexity: O(H), where H is the height of the tree. This space is used by the recursion call stack (recursive) or the manual stack (iterative). In a balanced BST, H is approximately log(N). In the worst case (a skewed tree, like a linked list), H is N, making the space complexity O(N).

Finally, remember that this property holds for any comparable data types, not just integers. If you build a BST of strings, an in-order traversal will yield the strings in alphabetical order, as demonstrated in the codebasics video (LINK, section from 22:03).

Conclusion

You have now completed the module on Binary Search Trees! In this lesson, you mastered one of the most elegant properties of a BST.

Key Takeaways:

• In-order traversal (LNR) on a Binary Search Tree always retrieves the elements in sorted ascending order.
• The recursive implementation is intuitive and directly follows the LNR definition.
• The iterative implementation using a stack is a crucial, non-trivial technique that avoids recursion limits and demonstrates a deeper understanding of stack-based algorithms.
• Both methods have a time complexity of O(N) and a space complexity of O(H).

Up Next:
You've built a solid foundation in trees, a hierarchical data structure. We are now ready to generalize these concepts to more complex structures. In the next module, we will begin our study of Graph Traversal Algorithms. You will find that tree traversals like DFS are special cases of graph traversal, and concepts like queues and stacks will be just as critical.