---
title: "Binary search tree"
url: https://algopath.pro/patterns/bst
language: en
summary: "A search tree keeps all the smaller values to the left and the larger ones to the right. Every lookup drops one whole side."
updated: 2026-08-24
---

# Binary search tree

A search tree keeps all the smaller values to the left and the larger ones to the right. Every lookup drops one whole side.

## How does Binary search tree work?

Every node splits its own subtree in two. Everything left is smaller, everything right is larger.

A search compares the target against the current node. That comparison picks one child and drops the other.

An insert walks the same path down. The new node becomes a child of the last node reached.

The rule covers whole subtrees, not just direct children. A left grandchild still has to be smaller than the root.

An in-order traversal reads the values in sorted order. That is the property most problems lean on.

Sorted input builds one long chain. Every operation then costs n, and balancing is the fix.

- `root = 5` Inserting 5, 3, 8 and 4. The first value becomes the root.
- `3 goes left` 3 is smaller than 5. It becomes the left child.
- `8 goes right` 8 is larger than 5. It becomes the right child.
- `4 goes left, then right` 4 is smaller than 5, then larger than 3.
- `in-order: 3, 4, 5, 8` Reading in order gives the values sorted.

## When should you use Binary search tree?

- binary search tree: left < node < right at every node
- insert/delete/search while keeping the data ordered
- validate BST / kth smallest / inorder traversal gives sorted order
- closest value or range query on a set that changes over time
- no array given up front, values arrive one at a time

## What is Binary search tree confused with?

- **Binary search (array)** - An array halves by index but cannot take a cheap insert. A tree halves by pointer and can.
- **Hash set / map** - A map is faster for an exact lookup. A tree also answers ranges and gives sorted order.
- **Binary heap / priority queue** - A heap only promises the smallest value at the root. A search tree orders every pair of nodes.
- **Tree traversal** - That page is about visiting a whole tree. This one is about the ordering rule.

## What is the time and space complexity of Binary search tree?

Balanced, n up to 1e6 gives O(log n) per operation. Unbalanced, the same tree degrades to O(n).

## A worked example of Binary search tree

### Check that a tree is a search tree

Decide whether a binary tree obeys the search tree rule.

Every value in the left subtree must be smaller. Every value on the right must be larger.

Comparing a node against its two children is not enough.

Carry a low and a high bound down the tree instead. Each step tightens one of the two.

```javascript
function isValidBST(root, low = -Infinity, high = Infinity) {
    if (!root) return true;

    // the bound comes from an ancestor, not from the parent alone
    if (root.val <= low || root.val >= high) return false;

    return isValidBST(root.left, low, root.val)
        && isValidBST(root.right, root.val, high);
}
```

## Common mistakes with Binary search tree

- **Checking only the direct children** A deep node can break the rule against a distant ancestor. Pass bounds down instead.
- **Assuming the tree is balanced** Sorted inserts build a chain, not a tree. Then log n is really n.
- **Leaving duplicates undecided** The problem has to say which side a repeated value goes. Pick a side and hold to it.
- **Deleting a node with two children carelessly** Its replacement is the in-order successor. Any other node breaks the ordering.

## Which interview problems use Binary search tree?

- **Validate binary search tree** Carry a low and a high bound down.
- **Search in a BST** One comparison drops half the tree.
- **Insert into a BST** Walk down and hang the node off the last one.
- **Delete node in a BST** Replace it with its in-order successor.
- **Kth smallest element in a BST** Stop the in-order walk after k nodes.
- **Lowest common ancestor of a BST** The first node that sits between the two values.
- **Convert sorted array to a BST** The middle element becomes the root, then recurse.

## JavaScript

```javascript
function insert(node, val) {
    if (!node) return { val, left: null, right: null };
    if (val < node.val) node.left = insert(node.left, val);
    else if (val > node.val) node.right = insert(node.right, val);
    return node;
}
```

## Python

```python
def insert(node, val):
    if not node:
        return TreeNode(val)
    if val < node.val:
        node.left = insert(node.left, val)
    elif val > node.val:
        node.right = insert(node.right, val)
    return node
```

## PHP

```php
function insert(?TreeNode $node, int $val): TreeNode {
    if ($node === null) return new TreeNode($val);
    if ($val < $node->val) $node->left = insert($node->left, $val);
    elseif ($val > $node->val) $node->right = insert($node->right, $val);
    return $node;
}
```