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.

Basic Implementation

basic.js 
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(", ")}]`);

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.
preorder Preorder records the current node before visiting left and right subtrees.