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 JavaScript 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.js
Replay: real traced execution (multi-file project)
class Node {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}
function render(node) {
  if (node === null) return "_";
  if (node.left === null && node.right === null) return String(node.value);
  return `${node.value}(${render(node.left)},${render(node.right)})`;
}
function sampleTree() {
  return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
}

const root = sampleTree();
const output = [];
function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }
preorder(root);
console.log(`[${output.join(", ")}]`);

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

    1class Node {2  constructor(value, left = null, right = null) {
    values this step4(2(1,3),6(5,7))tree[]output

  2. output ← [4]

    18const output = [];19function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }20preorder(root);
    values this step[] → [4]output4node

  3. output ← [4, 2]

    18const output = [];19function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }20preorder(root);
    values this step[4] → [4, 2]output2node

  4. output ← [4, 2, 1]

    18const output = [];19function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }20preorder(root);
    values this step[4, 2] → [4, 2, 1]output1node

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

    18const output = [];19function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }20preorder(root);
    values this step[4, 2, 1] → [4, 2, 1, 3]output3node

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

    18const output = [];19function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }20preorder(root);
    values this step[4, 2, 1, 3] → [4, 2, 1, 3, 6]output6node

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

    18const output = [];19function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }20preorder(root);
    values this step[4, 2, 1, 3, 6] → [4, 2, 1, 3, 6, 5]output5node

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

    18const output = [];19function preorder(node) { if (node === null) return; output.push(node.value); preorder(node.left); preorder(node.right); }20preorder(root);
    values this step[4, 2, 1, 3, 6, 5] → [4, 2, 1, 3, 6, 5, 7]output7node

  9. class Node

    1class Node {2  constructor(value, left = null, right = null) {
    values this step[4, 2, 1, 3, 6, 5, 7]output

Complexity

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

Implementation notes

  • The tree uses JavaScript Node objects with value, left, and right references. Missing children are null, and traversal reads references without mutating the tree.
  • preorder(node) is recursive. The base case node === null returns immediately; non-null frames push node.value, then recurse into node.left and node.right.
  • The output array stores Number values in visit order. Each recursive call creates a normal JavaScript stack frame, so runtime stack use follows the tree height.
  • The replay visits 4, 2, 1, 3, 6, 5, and 7, with output growing from [] to [4], [4, 2], [4, 2, 1], and finally [4, 2, 1, 3, 6, 5, 7].
  • console.log(\[${output.join(", ")}]`)formats the deterministic stdout[4, 2, 1, 3, 6, 5, 7]. Heap allocation is the seven-node sample tree, the output array, and the strings created by join` and the template literal.