Binary Search Trees

Lesson 3 of 7 in Recursion, Trees & Graphs · 35 min · Intermediate

A tree where left is smaller and right is bigger, all the way down.

Introduction

A phone book has to stay sorted while new names are added and old ones are crossed out all day. How do you keep it quick to search without re-sorting the whole thing every time?

Keep the names in a sorted list and finding one is quick: open in the middle, drop half, repeat. But adding a name in the middle means sliding every name after it down one slot, and removing one means sliding them all back.

Keep the names in a chain of cards instead, and adding or removing is a link or two. But now finding a name means starting at the first card and flipping through them one by one. Is there a layout that is quick at both jobs?

Lesson overview

This lesson will show you how to:

Explain the BST invariant: left values are smaller, right values larger.
Trace a search that goes left or right at each node.
Trace insertion of a new value down to its empty leaf spot.
Delete a node with zero, one or two children, using its in-order successor.
Explain why an in-order walk of a BST gives values in sorted order.
Spot when inserting sorted values leaves a BST lopsided and slow.

The picture

Binary tree with 6 nodes. Root 8. 8's children 3 and 10; 3's children 1 and 6; 10's right child 14.

Mental model

Think of a game of "higher or lower". At every node you hold one guess: if your number is lower you go through the left door, and if it is higher you go through the right door.

Each answer closes off a whole side of the tree, so you never look at most of it.

Every node asks "smaller or bigger?", and the answer rules out an entire subtree.

Words to know

BST invariant: For every node, all values in its left subtree are smaller and all values in its right subtree are bigger. It is about whole subtrees, not just the two children.
subtree: A node together with everything below it. Every node is the root of its own subtree.
in-order: Visit the left subtree, then the node, then the right subtree. On a BST this lists the values in sorted order.
in-order successor: The next bigger value after a node. When the node has a right subtree, it is the leftmost node in that subtree.
height: The number of links on the longest path from the root down to a leaf. Search, insert and delete take about this many steps.
balanced: Both sides of every node are about equally tall, so the height stays close to log n.
skewed: Leaning almost all one way, like a chain. Inserting values that are already sorted does this, and the height becomes n.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

Yes: You keep a collection of numbers sorted while values are added and removed, and you also look things up in it.
Yes: The problem hands you a TreeNode and says "binary search tree", or says the left side is smaller and the right side is bigger.
Yes: You need answers in order from a changing set: the next bigger value, the k-th smallest, everything in a range.
Yes: A sorted array would be perfect for lookups, but you would have to shift most of it on every insert or delete.

Not this when

No: The data never changes after you sort it: a sorted array with binary search is simpler and just as fast.
No: You only ask "is it in there?" and never need the order: a hash map answers in O(1) on average.
No: You only ever take the smallest or the largest item: a heap does that with less bookkeeping.

Which pattern fits?

Which pattern? 1 of 5
Numbers arrive one at a time and some are removed. At any moment you must be able to say which stored value is the smallest one bigger than x.
Which pattern? 2 of 5
A pool of tasks keeps changing. All you ever need is to remove the task with the smallest deadline, again and again.
Which pattern? 3 of 5
A sorted array of 100,000 ids never changes. Answer, as fast as possible, whether a given id is in it.
Which pattern? 4 of 5
Given the root of a binary tree, return its maximum depth, the number of nodes on the longest path from the root down to a leaf.
Which pattern? 5 of 5
Given the root of a binary search tree and an integer k, return the k-th smallest value in the tree.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode

1node = a new node holding val
1curr = root, parent = null
while curr is not null:
2if val < curr.val:
3parent = curr, curr = curr.left
4otherwise: parent = curr, curr = curr.right
5hang node under parent, on the side val belongs
6return root

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def insert_into_bst(root, val):
    node = TreeNode(val)
    if root is None:
        return node
    parent, curr = None, root
    while curr is not None:
        if val < curr.val:
            parent, curr = curr, curr.left
        else:
            parent, curr = curr, curr.right
    if val < parent.val:
        parent.left = node
    else:
        parent.right = node
    return root

Time · O(h): about O(log n) if balanced, O(n) in the worst caseSpace · O(1)

Search, insert and delete each walk one path from the root down, so they cost O(h), where h is the height.
h is about log n only while the tree stays balanced. Insert 1, 2, 3, 4, 5 in order and every value goes to the right of the last, so the tree is a chain and h is n. The Sorted input presets show it. Self-balancing trees (AVL, red-black) prevent this, and this lesson's plain BST does not.
Insert always ends in a new leaf and moves nothing else. This version sends a value equal to a node to the right; LeetCode's BST problems promise distinct values.
Delete has three cases: a leaf is cut off, a node with one child is replaced by that child, and a node with two children takes the value of its in-order successor, which is then removed as a leaf or a one-child node.
An in-order walk (left, node, right) of a BST visits the values in sorted order. That one fact solves k-th smallest, validate, and minimum difference.
To check a BST, compare each node with the whole range its ancestors allow, not just with its parent. Carry (lo, hi) down, and use null for "no bound yet" so INT_MIN and INT_MAX values still work.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode

Given the root of a binary search tree and an integer val, find the node whose value equals val and return the subtree rooted at that node. If there is no such node, return null.

Input

root = [4,2,7,1,3], val = 2

Output

[2,1,3]

Approach

Start at the root, 4, and ask the BST question: is 2 equal to, smaller than, or bigger than this node? (The code calls the value key.)
2 < 4, so everything in the right subtree (7) is bigger than 4 and cannot hold 2. Go left to 2.
2 == 2, so return this node. Its subtree, 2 with children 1 and 3, prints as [2,1,3].
If curr ever becomes null, the value isn't in the tree, so return null. Each step drops a whole subtree, so the work is at most the height of the tree.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def search_bst(root, key):
    curr = root
    while curr is not None:
        if key == curr.val:
            return curr
        if key < curr.val:
            curr = curr.left
        else:
            curr = curr.right
    return None

Time · O(h)Space · O(1)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

Which statement is the BST invariant?
You insert 1, 2, 3, 4, 5 in that order into an empty BST with no rebalancing. What does searching for 5 cost?
Why is the in-order successor a safe replacement when you delete a node with two children?
What do you get by visiting a BST in order: left subtree, then the node, then the right subtree?
A tree has root 10 and left child 5, and 5's right child is 12. Every child is on the correct side of its own parent (5 < 10, and 12 > 5). Is it a valid BST?

Question 1 of 5

Which statement is the BST invariant?

Every value in a node's left subtree is smaller than the node, and every value in its right subtree is bigger.The left subtree always has fewer nodes than the right subtree.Each node's left child is smaller than it, and its right child is bigger.The tree is as short as it can possibly be.

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

Solve Insert into a Binary Search Tree (opens in a new tab) (LeetCode, medium)
Hint: Walk down like a search. The first empty spot you reach is where the new leaf goes.
Solve Kth Smallest Element in a BST (opens in a new tab) (LeetCode, medium)
Hint: An in-order walk visits the values from smallest to largest, so stop at the k-th node you visit.
Solve Lowest Common Ancestor of a Binary Search Tree (opens in a new tab) (LeetCode, medium)
Hint: If both values are smaller than the node, go left, and if both are bigger, go right. Where they split is the answer.
Solve Convert Sorted Array to Binary Search Tree (opens in a new tab) (LeetCode, easy)
Hint: Pick the middle value as the root, and build each half of the array into a subtree the same way.
Solve Binary Search Tree Iterator (opens in a new tab) (LeetCode, medium)
Hint: It is an in-order walk you can pause. A stack that holds the path of left children is all the state you need.
Solve Minimum Absolute Difference in BST (opens in a new tab) (LeetCode, easy)
Hint: The closest pair of values are neighbours in sorted order, and an in-order walk hands you sorted order for free.
Solve Trim a Binary Search Tree (opens in a new tab) (LeetCode, medium)
Hint: If a node is below the range, its whole left subtree is too, so the answer can only come from its right side. Mirror that for a node above the range.
Solve Balance a Binary Search Tree (opens in a new tab) (LeetCode, medium)
Hint: Read the values out in order, then rebuild the tree from the middle of that sorted list, as when converting a sorted array.

Additional resources

Binary search tree (Wikipedia) (opens in a new tab) — Covers the ordering rule, the three operations and how balance affects their cost.
Binary search tree visualization (USF) (opens in a new tab) — Insert and delete values yourself and watch the tree restructure at each step.
VisuAlgo BST (visualgo.net) (opens in a new tab) — Animated BST searches, insertions and deletions with step controls you can pause and replay.
MIT OCW Introduction to Algorithms (6.006) (opens in a new tab) — Free lecture notes and videos that cover binary search trees and how they stay balanced.