Trees

BST Insert

Insert values into a binary search tree by comparing at each node.

Algorithm

Basic Implementation

basic.ts 
class Node {
  value: number;
  left: Node | null;
  right: Node | null;
  constructor(value: number, left: Node | null = null, right: Node | null = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}
function render(node: Node | null): string {
  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(): Node {
  return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
}

function insert(root, value) { if (root === null) return new Node(value); if (value < root.value) root.left = insert(root.left, value); else root.right = insert(root.right, value); return root; }
let root = null;
for (const value of [4, 2, 6, 1, 3, 5, 7]) root = insert(root, value);
console.log(render(root));

BST insertion is a comparison path. The pinned tree 4(2(1,3),6(5,7)) is shown with the inserted value taking its sorted slot.

Step 1 - Start at root

For value 5, compare with 4 first; 5 is larger, so move right.

First comparison: 5 > 4, so the search for the insert slot goes right.insert 54compare26137

Step 2 - Take the left slot under 6

At 6, value 5 is smaller, so it becomes the left child.

Second comparison: 5 < 6, so the open left slot is used.426compare135new7

Step 3 - Canonical tree

The resulting tree is the pinned shape 4(2(1,3),6(5,7)).

Final BST after 5 is present under 6.4261357

Complexity

  • Time: O(h) per insert
  • Space: O(n)

Implementation notes

  • Node is a TypeScript class with value: number, left: Node | null, and right: Node | null fields. The constructor defaults both child references to null.
  • The compact insert(root, value) helper in the checked source omits parameter annotations, but it operates on Node | null roots and numeric values. Inserting into null allocates new Node(value).
  • Recursive inserts mutate object references with root.left = insert(...) or root.right = insert(...), then return the same subtree root to the caller.
  • The comparison value < root.value sends smaller numbers left; the else branch sends greater values, and any duplicates, right.
  • The replay inserts 4, 2, 6, 1, 3, 5, and 7, ending with 4(2(1,3),6(5,7)). It also records sorted inserts [1, 2, 3, 4] forming the unbalanced chain 1(_,2(_,3(_,4))).
  • render(root) formats node references into 4(2(1,3),6(5,7)) for console.log. Visible allocation is the input literal, the allocated Node objects, and render/output strings; mutation is the left/right reference wiring.
binary search tree Values smaller than a node go left; larger values go right.