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].

in-order recursion The visit happens between the two recursive calls.

Basic Implementation

basic.py
Replay: real traced execution (multi-file project)
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)

  1. output ← [], tree ← 4(2(1,3),6(5,7))

    16output = []17def inorder(node):
    values this step[]output4(2(1,3),6(5,7))tree

  2. output ← [1]

    19    return20inorder(node.left)21output.append(node.value)
    values this step[] → [1]output

  3. output ← [1, 2]

    19    return20inorder(node.left)21output.append(node.value)
    values this step[1] → [1, 2]output

  4. output ← [1, 2, 3]

    19    return20inorder(node.left)21output.append(node.value)
    values this step[1, 2] → [1, 2, 3]output

  5. output ← [1, 2, 3, 4]

    19    return20inorder(node.left)21output.append(node.value)
    values this step[1, 2, 3] → [1, 2, 3, 4]output

  6. output ← [1, 2, 3, 4, 5]

    19    return20inorder(node.left)21output.append(node.value)
    values this step[1, 2, 3, 4] → [1, 2, 3, 4, 5]output

  7. output ← [1, 2, 3, 4, 5, 6]

    19    return20inorder(node.left)21output.append(node.value)
    values this step[1, 2, 3, 4, 5] → [1, 2, 3, 4, 5, 6]output

  8. output ← [1, 2, 3, 4, 5, 6, 7]

    19    return20inorder(node.left)21output.append(node.value)
    values this step[1, 2, 3, 4, 5, 6] → [1, 2, 3, 4, 5, 6, 7]output

  9. stdout ← [1, 2, 3, 4, 5, 6, 7]

    22    inorder(node.right)23inorder(root)24print(output)
    values this step[1, 2, 3, 4, 5, 6, 7]stdout[1, 2, 3, 4, 5, 6, 7]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.