Trees

BST Insert

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

Algorithm

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

binary search tree Values smaller than a node go left; larger values go right.

Visual walkthrough

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

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));

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.