Trees

Inorder Tree Traversal

Visit a binary tree's nodes in left-subtree, self, right-subtree order. For a binary search tree, this is the sorted sequence of values.

Algorithm

Canonical tree (((1) 2 (3)) 4 ((5) 6 (7))) finishes after seven node visits; the printed output is [1, 2, 3, 4, 5, 6, 7].

left, self, right For each node, recursively visit the left subtree first, then emit the node, then recursively visit the right subtree.
BST sortedness The lesson tree is a BST, so the inorder visit order is the same as sorting the values; the recursive descent makes the visit ordering explicit instead of leaning on `ORDER BY val`.

Basic Implementation

basic.sql
Replay: real traced execution (multi-file project)
.mode list
.headers off
CREATE TABLE node(idx INTEGER PRIMARY KEY, val INTEGER,
                  left_idx INTEGER, right_idx INTEGER);
INSERT INTO node(idx, val, left_idx, right_idx) VALUES
  (0, 1, NULL, NULL),
  (1, 3, NULL, NULL),
  (2, 2, 0, 1),
  (3, 5, NULL, NULL),
  (4, 7, NULL, NULL),
  (5, 6, 3, 4),
  (6, 4, 2, 5);

WITH RECURSIVE walk(idx, lo, hi) AS (
  SELECT 6, 0.0, 1.0
  UNION ALL
  SELECT
    CASE WHEN side.s = 'L' THEN n.left_idx ELSE n.right_idx END,
    CASE WHEN side.s = 'L' THEN walk.lo ELSE (walk.lo + walk.hi) / 2.0 END,
    CASE WHEN side.s = 'L' THEN (walk.lo + walk.hi) / 2.0 ELSE walk.hi END
  FROM walk
    JOIN node n ON n.idx = walk.idx
    CROSS JOIN (SELECT 'L' AS s UNION ALL SELECT 'R') side
  WHERE (side.s = 'L' AND n.left_idx IS NOT NULL)
     OR (side.s = 'R' AND n.right_idx IS NOT NULL)
)
SELECT '[' || GROUP_CONCAT(val, ', ') || ']'
FROM (
  SELECT n.val
  FROM walk JOIN node n ON n.idx = walk.idx
  ORDER BY (walk.lo + walk.hi) / 2.0
);

  1. node ← (empty)

    1.mode list2.headers off
    values this step(empty)node

  2. node ← (((1) 2 (3)) 4 ((5) 6 (7)))

    1.mode list2.headers off
    values this step(empty) → (((1) 2 (3)) 4 ((5) 6 (7)))node

  3. out ← [1]

    1.mode list2.headers off
    values this step[] → [1]out1next visit

  4. out ← [1, 2]

    1.mode list2.headers off
    values this step[1] → [1, 2]out2next visit

  5. out ← [1, 2, 3]

    1.mode list2.headers off
    values this step[1, 2] → [1, 2, 3]out3next visit

  6. out ← [1, 2, 3, 4]

    1.mode list2.headers off
    values this step[1, 2, 3] → [1, 2, 3, 4]out4next visit

  7. out ← [1, 2, 3, 4, 5]

    1.mode list2.headers off
    values this step[1, 2, 3, 4] → [1, 2, 3, 4, 5]out5next visit

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

    1.mode list2.headers off
    values this step[1, 2, 3, 4, 5] → [1, 2, 3, 4, 5, 6]out6next visit

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

    1.mode list2.headers off
    values this step[1, 2, 3, 4, 5, 6] → [1, 2, 3, 4, 5, 6, 7]out7next visit

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

    1.mode list2.headers off
    values this step[1, 2, 3, 4, 5, 6, 7]stdout[1, 2, 3, 4, 5, 6, 7]out

Complexity

  • Time: O(n)
  • Space: O(n) for the per-node (idx, lo, hi) rows in the CTE

Implementation notes

  • SQL: the tree is stored as node(idx, val, left_idx, right_idx) with NULL for missing children. A WITH RECURSIVE walk(idx, lo, hi) CTE descends the tree, assigning each node an interval (lo, hi) along the unit line. Descending left narrows the interval to (lo, mid); descending right narrows it to (mid, hi). The interval midpoint then sorts in inorder.
  • The single recursive arm joins walk to a two-row inline values table (SELECT 'L' UNION ALL SELECT 'R') so both children are expanded inside one CTE step; SQLite's recursive CTE one-reference rule is honoured because walk is only referenced by the join, not the inline values.
  • The final ORDER BY (walk.lo + walk.hi) / 2.0 projects the visited nodes back into inorder, and GROUP_CONCAT(val, ', ') emits [1, 2, 3, 4, 5, 6, 7] to match the lesson spec output.