Use BST properties for O(log n) search, validation, and ordered traversal.
A BST has the property: all left subtree values < root < all right subtree values. This enables O(log n) search, insert, and delete on average. Inorder traversal of a BST always yields a sorted sequence — this is the key insight for many BST problems.
O(log n) average, O(n) worst (unbalanced)
O(h) for recursion
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this when you need to check whether a value exists in a BST in O(log n) time
Compare the target with the current node value: if equal, found; if smaller, recurse left; if larger, recurse right. On a balanced BST this halves the search space at every step.
Problem Search in a Binary Search Tree. Traverse left when val < node.val and right when val > node.val; return the node when values match.
// BST search — Search in a Binary Search Tree
function searchBST(root, val) {
if (!root || root.val === val) return root;
return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}Use this when you need to confirm that a tree is a valid BST
Passing just the parent is insufficient because a node must satisfy constraints from all its ancestors. Instead, thread a min and max bound through the recursion: every left subtree node must be less than its ancestor, and every right subtree node must be greater.
Problem Validate Binary Search Tree. At each node, check node.val is strictly between the inherited min and max bounds.
// BST validation with bounds — Validate Binary Search Tree
function isValidBST(node, min = -Infinity, max = Infinity) {
if (!node) return true;
if (node.val <= min || node.val >= max) return false;
return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
}Use this when the problem requires the kth smallest element, detecting duplicate values, or converting a BST to a sorted array
Inorder traversal of a BST visits nodes in strictly ascending order, so the kth visited node is the kth smallest.
Problem Kth Smallest Element in a BST. Run inorder DFS, decrement a counter on each visit, and return when the counter hits zero.
// Inorder gives sorted sequence — Kth Smallest in BST
function kthSmallest(root, k) {
let count = 0, ans = null;
function inorder(n) {
if (!n || ans !== null) return;
inorder(n.left);
if (++count === k) { ans = n.val; return; }
inorder(n.right);
}
inorder(root);
return ans;
}Use this when you need the lowest common ancestor of two nodes in a BST
Unlike a general binary tree, you can use the BST ordering: if both target values are less than the current node, go left; if both are greater, go right; otherwise the current node is the split point and therefore the LCA.
Problem Lowest Common Ancestor of a BST.
// LCA in BST — using ordering property
function lowestCommonAncestor(root, p, q) {
if (p.val < root.val && q.val < root.val)
return lowestCommonAncestor(root.left, p, q);
if (p.val > root.val && q.val > root.val)
return lowestCommonAncestor(root.right, p, q);
return root;
}Use this when you need to maintain a BST under modifications
Insert: recurse to the correct leaf position and attach the new node. Delete: three cases: no children (remove), one child (splice out), two children (replace value with inorder successor then delete the successor).
Problem Delete Node in a BST. When deleting a node with two children, find the leftmost node in the right subtree (inorder successor), copy its value to the current node, then delete the successor.
// BST delete — Delete Node in a BST
function deleteNode(root, key) {
if (!root) return null;
if (key < root.val) root.left = deleteNode(root.left, key);
else if (key > root.val) root.right = deleteNode(root.right, key);
else {
if (!root.left) return root.right;
if (!root.right) return root.left;
let succ = root.right;
while (succ.left) succ = succ.left;
root.val = succ.val;
root.right = deleteNode(root.right, succ.val);
}
return root;
}Use this when you need to build a height-balanced BST from a sorted array
Always pick the middle element as the root so the left and right subtrees are equal in size (balanced). Recurse on the left half for the left subtree and the right half for the right subtree.
Problem Convert Sorted Array to Binary Search Tree. Mid index is (lo + hi) >> 1; left subtree uses indices lo..mid-1, right subtree uses mid+1..hi.
// Sorted array to balanced BST
function sortedArrayToBST(nums, lo = 0, hi = nums.length - 1) {
if (lo > hi) return null;
const mid = (lo + hi) >> 1;
const node = new TreeNode(nums[mid]);
node.left = sortedArrayToBST(nums, lo, mid - 1);
node.right = sortedArrayToBST(nums, mid + 1, hi);
return node;
}