Command Palette

Search for a command to run...

Hectal

Module 17

Binary Search Trees

Ordered trees: search and insert in O(h), validate with ranges, sorted order from in-order walks, and Java's TreeMap.

Intermediate 3 lessons 9 problems ~40 min of lessons
BST OrderingTree DFS

A binary search tree keeps one rule at every node: everything in the left subtree is smaller, everything in the right subtree is larger. That single rule lets you discard a whole subtree at each step, which is binary search on a tree, and it makes an in-order walk produce the values in sorted order.

This module covers search, insert and delete, validating the rule correctly (it's about ranges, not just parent and child), in-order tricks like the k-th smallest value, and the balanced BSTs you use every day through Java's TreeMap and TreeSet.

Best after: Binary Trees

Part 1

Learn the ideas

  1. 17.1The BST Rule, Search and InsertLeft is smaller, right is larger, at every node. Search and insert follow one path from the root, so they cost O(height).14 min
  2. 17.2Validating a BST with RangesChecking each node against its parent isn't enough. Every node must fall inside a range inherited from all of its ancestors.10 min
  3. 17.3In-Order Tricks and DeletingIn-order visits a BST in sorted order, which answers k-th smallest, closest values and successor questions. Deleting a node with two children borrows its in-order successor.14 min

Part 2

Solve the problems

In order of difficulty. Each one shows the pattern it teaches.

  1. 17.1Search in a Binary Search TreeEasyBST Ordering

    Following one path down the tree using the ordering.

  2. 17.2Insert into a Binary Search TreeMediumBST Ordering

    Insert = search until you fall off, then attach a leaf.

  3. 17.3Validate Binary Search TreeMediumBST Ordering

    Passing an allowed range down the tree.

  4. 17.4Kth Smallest Element in a BSTMediumBST Ordering

    In-order is sorted, so count as you walk and stop at k.

  5. 17.5Lowest Common Ancestor of a BSTMediumBST Ordering

    The ordering tells you where the split happens without searching subtrees.

  6. 17.6Convert Sorted Array to BSTEasyBST Ordering

    Building a balanced tree: the middle element is the root, and each half becomes a subtree.

  7. 17.7Two Sum in a BSTEasyBST Ordering

    Reusing array patterns on a tree: in-order gives a sorted list for two pointers, or a hash set during any traversal.

  8. 17.8Delete Node in a BSTMediumBST Ordering

    The three deletion cases, with the in-order successor for nodes that have two children.

  9. 17.9BST IteratorMediumBST Ordering

    Pausing an in-order traversal: keep the stack between calls so each next() is amortised O(1).