HTML5ANDCSS3Tools and Tutorials

HTML5ANDCSS3Tools and Tutorials

Binary Search Trees — DSA Tutorial - HTML5ANDCSS3

Trees

Binary Search Trees

Written by Swapnil RajaPublished 28 Aug 2026

A binary search tree is a sorted array that is cheap to insert into. Its whole advantage disappears the moment it becomes unbalanced, which happens on the most ordinary input there is: sorted data.

The one rule

For every node: everything in the left subtree is smaller, everything in the right subtree is larger. Applied recursively, at every node - not just the immediate children.

Search and insert

javascript

function search(node, target) {
  if (!node) return null
  if (node.value === target) return node

  // Half the tree is eliminated at every step.
  return target < node.value
    ? search(node.left, target)
    : search(node.right, target)
}

function insert(node, value) {
  if (!node) return new TreeNode(value)

  if (value < node.value) node.left = insert(node.left, value)
  else if (value > node.value) node.right = insert(node.right, value)

  return node   // equal values ignored
}

PreviousBinary Trees Explained NextCommon Tree Problems

Wrong, then right

javascript

// WRONG — passes a tree that is not a BST.
function isValidWrong(node) {
  if (!node) return true
  if (node.left && node.left.value >= node.value) return false
  if (node.right && node.right.value <= node.value) return false
  return isValidWrong(node.left) && isValidWrong(node.right)
}

// RIGHT — carry the allowed range down.
function isValid(node, min = -Infinity, max = Infinity) {
  if (!node) return true
  if (node.value <= min || node.value >= max) return false

  return isValid(node.left, min, node.value)
      && isValid(node.right, node.value, max)
}

//     5
//    / \
//   3   7
//      / \
//     2   8      <- 2 is right of 5, so this is NOT a BST
// isValidWrong says true. isValid says false.

The degenerate case

javascript

class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value; this.left = left; this.right = right
  }
}

function insert(node, value) {
  if (!node) return new TreeNode(value)
  if (value < node.value) node.left = insert(node.left, value)
  else if (value > node.value) node.right = insert(node.right, value)
  return node
}

let root = null
for (const n of [1, 2, 3, 4, 5]) root = insert(root, n)

// 1
//  \
//   2
//    \
//     3
//      \
//       4
//        \
//         5
// search(root, 5) now visits every node. O(n), not O(log n).