In-order Traversal of Binary Search Tree

In-order traversal is one of the fundamental tree traversal techniques. For a Binary Search Tree (BST), in-order traversal visits nodes in non-decreasing (ascending) order of their values. This makes it particularly useful for retrieving sorted data from a BST.

Traversal Order

In-order traversal follows the pattern: Left → Root → Right. For every node, you first visit its left subtree, then the node itself, and finally its right subtree.

Recursive Implementation

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def inorder_recursive(root, result=None):
    if result is None:
        result = []
    if root:
        inorder_recursive(root.left, result)
        result.append(root.val)
        inorder_recursive(root.right, result)
    return result

# Example usage
root = Node(5)
root.left = Node(3)
root.right = Node(8)
root.left.left = Node(2)
root.left.right = Node(4)

print(inorder_recursive(root))  # Output: [2, 3, 4, 5, 8]

Iterative Implementation (Using Stack)

def inorder_iterative(root):
    result = []
    stack = []
    current = root
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

# Output: [2, 3, 4, 5, 8]

Complexity

Key Properties

• For a BST, in-order traversal produces a sorted list of all values.
• It is often used to validate whether a binary tree is a BST (check if the traversal output is sorted).
• It is a depth-first traversal (DFS) technique.

Applications

• Extracting sorted data from a BST without additional sorting cost.
• Validating BST properties (checking if in-order output is strictly increasing).
• Finding the k-th smallest element in a BST (by stopping early during traversal).
• Tree serialization and deserialization.