Depth-First Search (DFS) in Binary Search Trees (BSTs)

Objective: Traverse BST nodes systematically, emphasizing depth-first exploration over breadth-first.

1. BST Traversal Overview

• In-Order Traversal: Visits nodes in sorted order (left → root → right).
• Key Use Case: Retrieve values in ascending/descending order, similar to iterating through a sorted array.

2. In-Order Traversal

Process

1. Recursively traverse the left subtree.
2. Process the current node (e.g., print or store its value).
3. Recursively traverse the right subtree.

Example

Tree:

      4
     / \\
    3   6
   /   / \\
  2   5   7

In-Order Output: 2, 3, 4, 5, 6, 7

Code

def in_order(root):
    if not root:
        return
    in_order(root.left)    # Traverse left
    print(root.val)        # Process node
    in_order(root.right)   # Traverse right

Time Complexity

• O(n): Visits every node once.