Skip to content
Tutorials Center
My learning

Topics

Lesson 94 of 225 ยท Trees

Binary Search Trees

Build a binary search tree in Python from scratch: insert, search, min and max, delete with all three cases, successor, validation and the degenerate worst case.

A binary search tree (BST) is a binary tree with one extra rule that makes searching fast: for every node, all keys in its left subtree are smaller, and all keys in its right subtree are larger. At each node you compare once and throw away one whole side, just like binary search on a sorted array. But unlike a sorted array, a BST also lets you insert and delete without shifting everything.

TEXT
          8
        /   \
       3     10
      / \      \
     1   6      14
        / \     /
       4   7   13

Look at node 6: its left subtree holds 4 (smaller), its right subtree holds 7 (larger). The rule holds for every node, not just the root's children. Node 4 is also less than 8 and greater than 3, because it sits in 3's right subtree inside 8's left subtree.

In this lesson you will implement search, insertion, minimum and maximum, deletion (the hard one), successor lookup and validation, and then see the one thing that can ruin a BST: a bad shape.

Start at the root and compare:

  • equal: found it;
  • target smaller: go left;
  • target larger: go right;
  • reached None: the key is not there.

Each step descends one level, so the cost is O(h), where h is the height. We will count comparisons in the code so you can see this.

Python BST node, insert and search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two things to notice. First, the inorder traversal prints the keys sorted, which is not an accident: left subtree, node, right subtree is ascending order under the BST rule. Second, insert returns the root of the subtree it was given, so the caller can write root.left = insert(root.left, key). That pattern handles the empty-tree case without special code.

The shape of the tree depends on the insertion order. The same nine keys inserted in a different order would produce a different tree, but always the same inorder list.

Insert (iteratively)

The recursive version is short, but an iterative one avoids recursion limits and is easy to write: walk down, remember the parent, and attach the new node where you fall off the tree.

Python Iterative insert, min and max

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The smallest key is the leftmost node, the largest is the rightmost. Both take O(h).

Deleting a node: three cases

Deletion is where most people stumble. Find the node first, then look at how many children it has.

TEXT
Case 1: leaf          Case 2: one child        Case 3: two children
   delete 4              delete 14                delete 3
                                                  replace 3 with its
 remove the node     replace the node with     inorder successor (4, the
                      its only child            smallest key in the right
                                                subtree), then delete that 4
  1. No children (a leaf): just remove it.
  2. One child: replace the node by that child (the child's subtree already satisfies the rule).
  3. Two children: you cannot simply remove it. Pick a stand-in that keeps the order: the inorder successor (the smallest key in the right subtree) or the inorder predecessor (the largest in the left subtree). Copy its key into the node, then delete the stand-in from the subtree. The stand-in has at most one child (a successor has no left child), so that deletion is case 1 or 2.
Python Delete from a BST (all three cases)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the final picture: after deleting 3, the key 6 took its place (6 was the smallest key in 3's right subtree), and the tree is still a valid BST. Deletion costs O(h): one walk down to find the node, and at most one more walk to find the successor.

A frequent bug is to delete the successor before copying its key, or to forget to reassign root.right = delete(root.right, ...). Remember the pattern: always assign the return value of the recursive call back to the child link.

Successor and predecessor

The inorder successor of a key is the next larger key in the tree. It appears in many questions (iterators, "next greater element in a BST", range queries). Two cases:

  1. If the node has a right subtree, the successor is the leftmost node of that subtree.
  2. Otherwise it is the lowest ancestor for which the node lies in the left subtree. On the way down from the root, remember the last node where you turned left.

Searching from the root with this rule needs no parent pointers.

Python Inorder successor and predecessor

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The largest key has no successor, the smallest has no predecessor; both print None.

Validating a BST

"Is this binary tree a valid BST?" is one of the most asked tree questions, and it has a famous wrong answer.

The tempting but wrong check: for every node, make sure left.key < node.key < right.key. This only compares a node with its children, so it misses violations that involve a more distant ancestor. Here is a tree it accepts wrongly:

TEXT
      5
     / \
    1   6
       / \
      3   7

Node 6 is greater than 5, and its children 3 and 7 satisfy 3 < 6 < 7. But 3 is in the right subtree of 5 and is smaller than 5, so the rule is broken.

The right idea: every node must lie inside an allowed range (low, high) that narrows as you descend. Going left sets high = node.key; going right sets low = node.key.

Alternative: inorder traversal of a valid BST is strictly increasing, so check that the traversal never goes down.

Python Validate a BST: wrong check vs ranges

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The naive check wrongly accepts the bad tree; the range and inorder checks both reject it. Both correct methods run in O(n) time and O(h) space.

When the BST goes wrong: the degenerate case

All the O(h) costs above are good news only if h is small. If you insert keys that are already sorted, every new key becomes the right child of the previous one, and the tree is a linked list with height n - 1. Search becomes O(n), no better than scanning an array.

Python Sorted input makes a chain

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With 255 keys, the same data gives a chain of height 254 or a perfect tree of height 7. This is why production systems use self-balancing trees such as AVL and red-black trees, which fix their shape automatically after each insert and delete.

BST versus the alternatives

Structure Search Insert Delete Sorted iteration
Sorted array O(log n) O(n) O(n) O(n)
Hash table (dict) O(1) average O(1) average O(1) average needs a sort, O(n log n)
BST, balanced O(log n) O(log n) O(log n) O(n)
BST, degenerate O(n) O(n) O(n) O(n)

Choose a BST (really, a balanced one) when you need keys in order while the data keeps changing: nearest key, "all keys between a and b", smallest key greater than x. For plain lookups, a dictionary is simpler and faster. Python's standard library has no BST; for a static sorted sequence use bisect, and for a dynamic one people use the third-party sortedcontainers package.

Common mistakes

  • Validating only parent-child pairs. Use ranges or an inorder pass.
  • Forgetting to reassign the child link after a recursive insert or delete.
  • Mishandling duplicates. Decide the policy (ignore, count, or always go right) and apply it everywhere, including validation (< vs <=).
  • Deleting a two-child node by detaching it. That loses its subtrees; use the successor.
  • Assuming O(log n). Plain BSTs give O(h); only balanced ones guarantee O(log n).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does an inorder traversal of a valid BST produce?

    Everything in the left subtree is smaller and everything in the right is larger, so left, node, right is ascending.
  2. 2. A node with two children is deleted from a BST. What replaces its key?

    The inorder successor or predecessor keeps the BST rule intact, and it has at most one child, so deleting it is easy.
  3. 3. The keys 1, 2, 3, 4, 5 are inserted into an empty plain BST in this order. What is the tree's height (in edges)?

    Each key is larger than all previous ones, so each becomes the right child of the last: a chain of 5 nodes with 4 edges.
  4. 4. Why is checking left.key < node.key < right.key at each node not enough to validate a BST?

    A key deep in the right subtree can be smaller than the root while still looking fine next to its own parent. Ranges carry the ancestors' limits downward.
  5. 5. What is the worst-case time of search in a plain (unbalanced) BST with n keys?

    Search costs O(h), and the height can be n - 1 for a chain.

Summary

  • A BST keeps smaller keys on the left and larger keys on the right of every node; inorder traversal yields sorted keys.
  • Search, insert, minimum and maximum each walk one root-to-leaf path: O(h).
  • Delete has three cases: leaf, one child, two children (replace by the inorder successor, then delete it).
  • Successor: leftmost node of the right subtree, or the last node where you turned left.
  • Validate with ranges (or an increasing inorder), never by looking only at children.
  • Sorted insertion creates a chain with O(n) operations; balanced trees (AVL, red-black) guarantee O(log n).
  • More tree questions are in common tree problems.

Next: Common Tree Problems