Trees

Preorder Traversal

Visit the root before each subtree, producing root-left-right order.

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.

preorder Preorder records the current node before visiting left and right subtrees.

Basic Implementation

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

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

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

  2. output ← [4]

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

  3. output ← [4, 2]

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

  4. output ← [4, 2, 1]

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

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

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

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

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

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

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

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

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

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

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

Complexity

  • Time: O(n)
  • Space: O(h) recursion stack

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.