Trees

BST Insert

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

Algorithm

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

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

  • Each tree node is a JavaScript Node object with value, left, and right properties. Missing children are stored as null, and inserting into a null slot allocates a new node.
  • insert(root, value) is recursive and returns the subtree root after any mutation. The caller assigns root = insert(root, value), and recursive frames update references with root.left = ... or root.right = ....
  • Comparisons use numeric Number ordering. Values smaller than root.value go left; the else branch sends greater values, and any duplicate values, to the right.
  • The replay inserts 4 at the root, then 2 left, 6 right, 1 under 2.left, 3 under 2.right, 5 under 6.left, and 7 under 6.right, ending with 4(2(1,3),6(5,7)).
  • render(root) recursively formats node references instead of printing object identities, and console.log prints 4(2(1,3),6(5,7)). Heap allocation includes the input literal, the seven Node objects, and the strings created while rendering; the replay also shows sorted inserts forming the unbalanced chain 1(_,2(_,3(_,4))).
binary search tree Values smaller than a node go left; larger values go right.