Introduction to Binary Search Trees

EditorialUpdated Oct 31, 2026

Binary search, kept in a tree

In a sorted array, binary search compares with the middle value and throws away the half that can't hold the answer. A binary search tree keeps that decision in its shape: every value smaller than a node is in its left subtree, every value bigger is in its right subtree. So each comparison throws away a whole subtree, and a search is one walk down from the root:

A binary search tree, 8 at the root, 3 and 10 below it, then 1, 6 and 14, then 4, 7 and 13. A search for 13 is drawn as a path down 8, 10, 14 and 13, in four comparisons. The subtrees it never visits, 3's whole subtree and nothing else, are greyed out and labelled ruled out.

Every node, not only its children

The rule is about whole subtrees: for every node, everything in its left subtree is smaller and everything in its right subtree is bigger. Checking each node against its own children isn't enough. In [5, 3, 8, 1, 6], 3 is less than 5 and 1 and 6 are on the correct sides of 3, yet 6 sits in 5's left subtree:

The tree 5 with children 3 and 8, and 3 with children 1 and 6. Each child is on the correct side of its own parent, but 6 is circled in red inside 5's left subtree, where only values smaller than 5 belong. A search for 6 is drawn going right at 5, to 8, and finding nothing.

A search for 6 in it goes right at 5, because 6 is bigger, and never finds it: the search printed False. Its inorder came out [1, 3, 6, 5, 8], not sorted. Every operation in this section relies on the whole-subtree rule, which is why validating a tree (in BST Operations: Delete, Validate and Walk in Order) has to check ranges, not children.

Search and insert

Search walks down: equal, and it's found; smaller, go left; bigger, go right. If the walk runs off the tree, the value isn't there. Insert is the same walk: when it reaches the empty place where the value would have been, it hangs a new node there. Both are loops, with nothing to remember on the way down:

// Search: at each node, go left for a smaller value and right for a bigger one.
TreeNode* searchBST(TreeNode* root, int val) {
    TreeNode* node = root;
    while (node != nullptr && node->val != val)
        node = val < node->val ? node->left : node->right;
    return node;                                  // the node holding val, or nullptr
}

// Insert: walk the same way to the empty place where val belongs, and hang it there.
TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (root == nullptr) return new TreeNode(val);
    TreeNode* node = root;
    while (true) {
        if (val < node->val) {
            if (node->left == nullptr) { node->left = new TreeNode(val); break; }
            node = node->left;
        } else {
            if (node->right == nullptr) { node->right = new TreeNode(val); break; }
            node = node->right;
        }
    }
    return root;
}

def search_bst(root, val):
    """At each node, go left for a smaller value and right for a bigger one."""
    node = root
    while node is not None and node.val != val:
        node = node.left if val < node.val else node.right
    return node                                   # the node holding val, or None


def insert_into_bst(root, val):
    """Walk the same way to the empty place where val belongs, and hang it there."""
    if root is None:
        return TreeNode(val)
    node = root
    while True:
        if val < node.val:
            if node.left is None:
                node.left = TreeNode(val)
                return root
            node = node.left
        else:
            if node.right is None:
                node.right = TreeNode(val)
                return root
            node = node.right

// Search: at each node, go left for a smaller value and right for a bigger one.
static TreeNode searchBST(TreeNode root, int val) {
    TreeNode node = root;
    while (node != null && node.val != val)
        node = val < node.val ? node.left : node.right;
    return node;                                  // the node holding val, or null
}

// Insert: walk the same way to the empty place where val belongs, and hang it there.
static TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    TreeNode node = root;
    while (true) {
        if (val < node.val) {
            if (node.left == null) { node.left = new TreeNode(val); break; }
            node = node.left;
        } else {
            if (node.right == null) { node.right = new TreeNode(val); break; }
            node = node.right;
        }
    }
    return root;
}

// Search: at each node, go left for a smaller value and right for a bigger one.
function searchBST(root, val) {
    let node = root;
    while (node !== null && node.val !== val)
        node = val < node.val ? node.left : node.right;
    return node;                                  // the node holding val, or null
}

// Insert: walk the same way to the empty place where val belongs, and hang it there.
function insertIntoBST(root, val) {
    if (root === null) return new TreeNode(val);
    let node = root;
    while (true) {
        if (val < node.val) {
            if (node.left === null) { node.left = new TreeNode(val); break; }
            node = node.left;
        } else {
            if (node.right === null) { node.right = new TreeNode(val); break; }
            node = node.right;
        }
    }
    return root;
}

Each printed the subtree it found or the tree it built, as LeetCode's list: [2, 1, 3] for 2 in Search in a Binary Search Tree's example, [] for 5, which isn't there, then Insert into a Binary Search Tree's two examples and an insert into an empty tree. Step through a search:

Searching for 13 — Indigo is the node being compared; grey, the subtrees ruled out; green, the value found.

The smallest value is as far left as the tree goes, and the largest as far right:

def min_max(root):
    """The smallest value is as far left as the tree goes, the largest as far right."""
    low = high = root
    while low.left is not None:
        low = low.left
    while high.right is not None:
        high = high.right
    return [low.val, high.val]

On [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13] it returned [1, 14]. All of these walk one path down, so each costs O(h), the height of the tree.

Floor and ceiling

The floor of x is the largest value that isn't bigger than x; the ceiling is the smallest value that isn't smaller. Walk down as in a search, but keep the best answer seen. For the floor, a value up to x is a candidate, and a bigger candidate can only be on its right; a value bigger than x sends the walk left. The ceiling is the mirror image:

// The largest value <= x, or -1: a node <= x is a candidate, and a bigger one can only be on its right.
int floorInBST(TreeNode* root, int x) {
    int best = -1;
    for (TreeNode* node = root; node != nullptr;) {
        if (node->val <= x) { best = node->val; node = node->right; }
        else node = node->left;
    }
    return best;
}

// The smallest value >= x, or -1: the mirror image.
int ceilInBST(TreeNode* root, int x) {
    int best = -1;
    for (TreeNode* node = root; node != nullptr;) {
        if (node->val >= x) { best = node->val; node = node->left; }
        else node = node->right;
    }
    return best;
}

def floor_in_bst(root, x):
    """The largest value <= x, or -1: a node <= x is a candidate, and a bigger one can only be on its right."""
    best, node = -1, root
    while node is not None:
        if node.val <= x:
            best, node = node.val, node.right
        else:
            node = node.left
    return best


def ceil_in_bst(root, x):
    """The smallest value >= x, or -1: the mirror image."""
    best, node = -1, root
    while node is not None:
        if node.val >= x:
            best, node = node.val, node.left
        else:
            node = node.right
    return best

// The largest value <= x, or -1: a node <= x is a candidate, and a bigger one can only be on its right.
static int floorInBST(TreeNode root, int x) {
    int best = -1;
    for (TreeNode node = root; node != null;) {
        if (node.val <= x) { best = node.val; node = node.right; }
        else node = node.left;
    }
    return best;
}

// The smallest value >= x, or -1: the mirror image.
static int ceilInBST(TreeNode root, int x) {
    int best = -1;
    for (TreeNode node = root; node != null;) {
        if (node.val >= x) { best = node.val; node = node.left; }
        else node = node.right;
    }
    return best;
}

// The largest value <= x, or -1: a node <= x is a candidate, and a bigger one can only be on its right.
function floorInBST(root, x) {
    let best = -1;
    for (let node = root; node !== null;) {
        if (node.val <= x) { best = node.val; node = node.right; }
        else node = node.left;
    }
    return best;
}

// The smallest value >= x, or -1: the mirror image.
function ceilInBST(root, x) {
    let best = -1;
    for (let node = root; node !== null;) {
        if (node.val >= x) { best = node.val; node = node.left; }
        else node = node.right;
    }
    return best;
}

Each printed 2 3 6 -1 -1: the floor of 3 is 2 and the ceiling of 3 is 3 in Floor in BST and Ceil in BST's examples, the floor of 6 is 6 itself, and with no value small or big enough the answer is -1. Step through the floor of 5:

The floor of 5 — Indigo is the node being compared; green, the best candidate so far.

Inorder is sorted

Inorder visits a node's left subtree, the node, then its right subtree. In a binary search tree everything on the left is smaller and everything on the right bigger, so inorder visits the values in increasing order:

def inorder(node, out):
    if node is not None:
        inorder(node.left, out)
        out.append(node.val)              # everything on the left is smaller, everything after it bigger
        inorder(node.right, out)
    return out

On [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13] it returned [1, 3, 4, 6, 7, 8, 10, 13, 14]. On a tree of 100,000 values inserted in random order, the inorder matched the sorted values exactly. That's the tool behind the next lesson's kth smallest value, the successor of a node, and checking that a tree is a binary search tree at all.

The height is everything

Every operation so far is one walk down, so each costs the height. The height depends on the order the values arrived in. Inserted in random order, a tree stays bushy; inserted in sorted order, each new value is the biggest so far and goes to the right of the last, and the tree is a chain:

Two panels. Left: the values 1 to 7 inserted in sorted order make a chain leaning right, height 6. Right: the same values inserted as 4, 2, 6, 1, 3, 5, 7 make a full tree of height 2. Under each, the order they were inserted in.

Measured in Python: n values inserted, then n searches for random values:

Nodes	Inserted in random order	Inserted in sorted order
1,000	height 19, 1.8 ms	height 999, 44.5 ms
2,000	height 24, 2.9 ms	height 1,999, 177.3 ms
4,000	height 26, 6.5 ms	height 3,999, 720.0 ms

A random search took 14.3 comparisons on average in the random tree of 4,000, and 2,020 in the chain. With 100,000 values in random order the height was 44: a random tree stays close to log n, but nothing makes the input random. Sorted input, or nearly sorted, is common, and it turns every operation into O(n). Balanced Trees and Ordered Sets is about the trees that rotate to stay short.

The chain also breaks recursion. The recursive insert, node.left = insert(node.left, val), goes as deep as the tree, and in Python it stopped with a RecursionError on the 998th sorted value. The loops above have no depth.

def insert_into_bst(node, val):
    if node is None:
        return TreeNode(val)
    if val < node.val:
        node.left = insert_into_bst(node.left, val)
    else:
        node.right = insert_into_bst(node.right, val)
    return node

Now you insert and search

Below, you are the walk. The next value to insert waits above the tree; at each node, click the child it goes to, or the empty place where it belongs. A wrong side is refused, with the comparison. Then insert the same values in sorted order and watch the height, and search for a value that isn't there.

Insert and Search: route each value down the tree yourself

Spotting it, and when it breaks

The clues. "Binary search tree" in the problem, or values kept in order with inserts and removals between queries. "Closest value", "the largest value no bigger than", "the smallest value at least": floor and ceiling. "In sorted order": inorder.

The near-misses. A plain binary tree has no order, so a search there visits every node (Binary Trees). A heap orders each node only against its children, the weaker check above, so it can find the smallest value fast and nothing else (Heaps). A sorted array answers the same queries with binary search, but an insert shifts everything after it.

When it breaks. Sorted or nearly sorted input makes a chain, and every operation O(n); recursion on that chain runs out of stack. Duplicates need a rule: Insert into a Binary Search Tree promises a new value, but in general, pick a side or keep a count.

Bugs that cost a submission

Dropping the recursive call's answer.

def search_bst(node, val):
    if node is None or node.val == val:
        return node
    if val < node.val:
        search_bst(node.left, val)        # the answer comes back here, and is dropped
    else:
        search_bst(node.right, val)

Searching for 2 in [4, 2, 7, 1, 3] returned []: the call one level down found 2 and returned it to a caller that ignored it. Write return search_bst(node.left, val).

Making the new node and never linking it.

def insert_into_bst(node, val):
    if node is None:
        return TreeNode(val)
    if val < node.val:
        insert_into_bst(node.left, val)   # the new node is made, and never linked
    else:
        insert_into_bst(node.right, val)
    return node

Inserting 5 into [4, 2, 7, 1, 3] left it as [4, 2, 7, 1, 3]: the new node was returned to a caller that dropped it. Assign it, node.left = insert_into_bst(node.left, val).

Taking the first candidate as the floor.

def floor_in_bst(root, x):
    node = root
    while node is not None:
        if node.val <= x:
            return node.val               # the first value <= x, not the largest
        node = node.left
    return -1

The floor of 7 in [8, 5, 9, 2, 6, null, 10] came out 5; it's 6. 5 is a candidate, but a bigger one can be on its right: keep walking.

Check yourself

Quiz

1 / 6

Multiple choice

In a binary search tree, which values can be in a node's left subtree?

Practice problems

In this order:

BST Fundamentals & Properties: insert, then read the tree back in order.
Search in a Binary Search Tree: one walk down.
Minimum & Maximum in a BST: as far left, as far right.
Ceil in BST and 5. Floor in BST: keep the best candidate as you walk.
Insert into a Binary Search Tree: the search, then one link.

Next, BST Operations: Delete, Validate and Walk in Order: taking a node out, checking the rule, and walking the tree in sorted order one step at a time.