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.dart 
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);
}

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.
in-order recursion The visit happens between the two recursive calls.