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

Basic Implementation

basic.sql

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

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.

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