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.dart
Replay: real traced execution (multi-file project)
class TreeNode {
  int value;
  TreeNode? left;
  TreeNode? right;
  TreeNode(this.value, this.left, this.right);
}

void main() {
  final n1 = TreeNode(1, null, null);
  final n3 = TreeNode(3, null, null);
  final n2 = TreeNode(2, n1, n3);
  final n5 = TreeNode(5, null, null);
  final n7 = TreeNode(7, null, null);
  final n6 = TreeNode(6, n5, n7);
  final root = TreeNode(4, n2, n6);

  final output = <int>[];
  void inorder(TreeNode? node) {
    if (node == null) {
      return;
    }
    inorder(node.left);
    output.add(node.value);
    inorder(node.right);
  }
  inorder(root);
  print(output);
}

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

    17final output = <int>[];18void inorder(TreeNode? node) {
    values this step[]output4(2(1,3),6(5,7))tree

  2. output ← [1]

    22inorder(node.left);23output.add(node.value);24inorder(node.right);
    values this step[] → [1]output

  3. output ← [1, 2]

    22inorder(node.left);23output.add(node.value);24inorder(node.right);
    values this step[1] → [1, 2]output

  4. output ← [1, 2, 3]

    22inorder(node.left);23output.add(node.value);24inorder(node.right);
    values this step[1, 2] → [1, 2, 3]output

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

    22inorder(node.left);23output.add(node.value);24inorder(node.right);
    values this step[1, 2, 3] → [1, 2, 3, 4]output

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

    22inorder(node.left);23output.add(node.value);24inorder(node.right);
    values this step[1, 2, 3, 4] → [1, 2, 3, 4, 5]output

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

    22inorder(node.left);23output.add(node.value);24inorder(node.right);
    values this step[1, 2, 3, 4, 5] → [1, 2, 3, 4, 5, 6]output

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

    22inorder(node.left);23output.add(node.value);24inorder(node.right);
    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]

    26  inorder(root);27  print(output);28}
    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

  • Dart: write the recursion explicitly as a local function inside main so it can close over the output list. A sync* generator would technically work but hides 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.