Binary Search Tree
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
Define the node and tree
A BST node holds a value and left/right child pointers. The tree itself starts with a null root.
Codeclass 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
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.
Codeinsert(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.
Hint
Equal values go to the right (or left — pick a convention and stick with it).
- 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.
Hint
The search path is at most the height of the tree — O(log n) for a balanced tree.
- 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.
Hint
The base case is a null node — just return.
- 5
Test the BST
Insert several values, search for present and absent values, and confirm in-order traversal gives sorted output.
Codeconst 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
class TreeNode { constructor(v) { this.value = v; this.left = null; this.right = null; } }
class BinarySearchTree {
constructor() { this.root = null; }
// TODO: insert, search, inOrder
}class TreeNode { constructor(v) { this.value=v; this.left=null; this.right=null; } }
class BinarySearchTree {
constructor() { this.root = null; }
insert(v) { const n = new TreeNode(v); if (!this.root) { this.root = n; return this; } const r = (c) => { if (v < c.value) { if (!c.left) c.left = n; else r(c.left); } else { if (!c.right) c.right = n; else r(c.right); } }; r(this.root); return this; }
search(v) { const r = (c) => { if (!c) return false; if (v === c.value) return true; return v < c.value ? r(c.left) : r(c.right); }; return r(this.root); }
inOrder() { const r = []; const v = (c) => { if (!c) return; v(c.left); r.push(c.value); v(c.right); }; v(this.root); return r; }
}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
Related Glossary
- Binary Search Tree
A sorted binary tree enabling O(log n) search.
Related Glossary
A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.
- Binary Search Tree
A sorted binary tree enabling O(log n) search.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.