Trees

In-Order Traversal (BST)

Recurse left, visit the node, recurse right. On a binary search tree the visit order is the values in ascending order — a key invariant that makes in-order traversal useful for BSTs specifically.

Algorithm

The canonical 7-node BST is built inline (root 4, left subtree with 1, 2, 3, right subtree with 5, 6, 7). In-order visit produces [1, 2, 3, 4, 5, 6, 7].

Basic Implementation

basic.py 
class Node:
    __slots__ = ("value", "left", "right")
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

n1 = Node(1)
n3 = Node(3)
n2 = Node(2, n1, n3)
n5 = Node(5)
n7 = Node(7)
n6 = Node(6, n5, n7)
root = Node(4, n2, n6)

output = []
def inorder(node):
    if node is None:
        return
    inorder(node.left)
    output.append(node.value)
    inorder(node.right)
inorder(root)
print(output)

Complexity

  • Time: O(n)
  • Space: O(h) for the call stack

Implementation notes

  • Python: write the recursion explicitly. Do not delegate to a generator expression — the lesson focuses on the order of visit vs. the two recursive calls.
  • The replay emits one frame per visit(node) and shows the running output list, matching the lesson spec.
in-order recursion The visit happens between the two recursive calls.