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

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