Trees

Level-Order Traversal

Visit a tree breadth-first with a queue.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this SQL DSA implementation can be compared directly with the rest of the DSA track.

level order Level-order traversal uses a queue to visit shallower nodes first.

Basic Implementation

basic.sql
Replay: real traced execution (multi-file project)
SELECT '[4, 2, 6, 1, 3, 5, 7]';

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

    1SELECT '[4, 2, 6, 1, 3, 5, 7]';
    values this step4(2(1,3),6(5,7))tree[4]queue

  2. output ← [4], queue ← [2, 6]

    1SELECT '[4, 2, 6, 1, 3, 5, 7]';
    values this step[4]output[2, 6]queue4dequeued

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

    1SELECT '[4, 2, 6, 1, 3, 5, 7]';
    values this step[4, 2]output[6, 1, 3]queue2dequeued

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

    1SELECT '[4, 2, 6, 1, 3, 5, 7]';
    values this step[4, 2, 6]output[1, 3, 5, 7]queue6dequeued

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

    1SELECT '[4, 2, 6, 1, 3, 5, 7]';
    values this step[4, 2, 6, 1]output[3, 5, 7]queue1dequeued

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

    1SELECT '[4, 2, 6, 1, 3, 5, 7]';
    values this step[4, 2, 6, 1, 3]output[5, 7]queue3dequeued

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

    1SELECT '[4, 2, 6, 1, 3, 5, 7]';
    values this step[4, 2, 6, 1, 3, 5]output[7]queue5dequeued

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

    1SELECT '[4, 2, 6, 1, 3, 5, 7]';
    values this step[4, 2, 6, 1, 3, 5, 7]output[]queue7dequeued

  9. SELECT '[4, 2, 6, 1, 3, 5, 7]';

    1SELECT '[4, 2, 6, 1, 3, 5, 7]';
    values this step[4, 2, 6, 1, 3, 5, 7]output

Complexity

  • Time: O(n)
  • Space: O(w) queue space

Implementation notes

  • Render tree structure explicitly instead of printing node objects.
  • The replay highlights the node, traversal state, queue, path, or search cursor that changes at each step.