Skip to content

Binary Search Tree

Medium ~40 min

What you'll build

A BinarySearchTree class where left children are smaller and right children are larger, supporting insert, search, and in-order traversal (which yields sorted output).

Goals

  • Model a tree node with left and right children
  • Insert values maintaining the BST property
  • Search using the divide-and-conquer property
  • Traverse in-order to produce sorted output

Prerequisites

  • Recursion (base case + recursive call)
  • Objects and property access
  • Comparison operators

Steps

  1. 1

    Define the node and tree

    A BST node holds a value and left/right child pointers. The tree itself starts with a null root.

    Code
    class TreeNode {
      constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
      }
    }
    
    class BinarySearchTree {
      constructor() { this.root = null; }
    }

    Expected result

    An empty BST with root === null.

  2. 2

    Implement insert recursively

    To insert, compare the value to the current node: go left if smaller, right if larger. When you reach null, place the new node there. Write a recursive helper.

    Code
    insert(value) {
      const node = new TreeNode(value);
      if (!this.root) { this.root = node; return this; }
      const recurse = (current) => {
        if (value < current.value) {
          if (!current.left) current.left = node;
          else recurse(current.left);
        } else {
          if (!current.right) current.right = node;
          else recurse(current.right);
        }
      };
      recurse(this.root);
      return this;
    }

    Expected result

    insert(5).insert(3).insert(7) builds a tree with 5 at root, 3 left, 7 right.

  3. 3

    Implement search

    Search uses the same comparison logic: at each node, go left if the target is smaller, right if larger, return true if equal, false if you reach null.

  4. 4

    Implement in-order traversal

    In-order traversal visits left subtree, then node, then right subtree. For a BST this yields values in sorted order. Write it recursively.

  5. 5

    Test the BST

    Insert several values, search for present and absent values, and confirm in-order traversal gives sorted output.

    Code
    const bst = new BinarySearchTree();
    [5, 3, 7, 1, 4, 6, 8].forEach(v => bst.insert(v));
    console.log(bst.search(4)); // true
    console.log(bst.search(9)); // false
    console.log(bst.inOrder()); // [1, 3, 4, 5, 6, 7, 8]

    Expected result

    search(4) returns true, search(9) returns false, inOrder returns sorted array.

Try it yourself

What you learned

You built a tree and used recursion to maintain its ordering invariant — BSTs power database indexes, set/map implementations, and many divide-and-conquer algorithms.

Related Resources

Related Lessons

  • Recursion

    Insert, search, and traversal are all recursive.

  • Objects

    Each node is an object with value and children.

Related Glossary

Related Glossary

A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors

← Back to topic