Trees

BST Search

Search a binary search tree for one present and one absent value.

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

const root = sampleTree();
function search(root, target) { let node = root; while (node !== null) { if (target === node.value) return true; node = target < node.value ? node.left : node.right; } return false; }
console.log(search(root, 5) ? "5 found" : "5 not found");
console.log(search(root, 8) ? "8 found" : "8 not found");

A BST search follows one comparison path. The same pinned tree shows a found path for 5 and a missing path for 8.

Step 1 - Find 5

Search 5 takes right from 4, then left from 6, then matches 5.

Present search path: 4 -> 6 -> 5.4#126#2135match7

Step 2 - Miss 8

Search 8 takes right from 4, right from 6, right from 7, then reaches null.

Absent search path: 4 -> 6 -> 7 -> null.4#126#21357#3nullnot found

Complexity

  • Time: O(h) per search
  • Space: O(1) iterative

Implementation notes

  • The searched tree is built from JavaScript Node objects with value, left, and right properties. Missing children are null, and the search reads existing references without allocating or mutating nodes.
  • search(root, target) is iterative: let node = root holds the current cursor, and while (node !== null) stops when a missing child is reached.
  • Comparisons use Number semantics. target === node.value returns true; otherwise target < node.value ? node.left : node.right chooses the next reference, so smaller targets move left and larger targets move right.
  • The replay searches 5 through cursors 4 -> right, 6 -> left, then 5 -> match. It searches missing 8 through 4 -> right, 6 -> right, 7 -> right, then reaches null and returns false.
  • The two console.log calls format booleans into 5 found and 8 not found, producing stdout 5 found\n8 not found. The material heap allocation is the seven-node sample tree; the search itself only updates the cursor binding.
search path A comparison chooses one subtree at each step, so whole branches are skipped.