Core · Module 10 · Lesson 2 of 5

Binary search trees

A binary search tree keeps smaller keys to the left of each node and larger keys to the right, so a search discards a whole subtree at every step. Its speed depends entirely on its height.

ProAbout 13 minutes

By the end you can

State the binary search tree property and check it correctly
Search for a key, find the minimum and maximum, and find a key's successor
Explain why every operation costs O(height), and how the order of insertions sets the height

Builds on Vocabulary and traversals, Binary search without off-by-one bugs.

01 · A question first

A sorted array finds a key in O(log n) but needs O(n) to insert one. A hash table inserts in O(1) but can't tell you the smallest key above 50. A binary search tree aims to do both kinds of work in O(log n). What does it store at each node to make that possible, and when does the promise fail?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

The search tree property
Searching
Ordered operations
Height is everything
Storing more in each node
BST or hash table?
Pseudocode & Multi-Language Implementations (C++, Java, Python)
Complexity Derivation, Edge Cases & Common Mistakes

See plans Already a member? Sign in

03 · Practice

Practice · medium · LeetCodeValidate binary search treeDecide whether a binary tree is a valid binary search tree by passing down the range each subtree must lie in.Practice · medium · LeetCodeKth smallest element in a BSTFind the kth smallest key in a binary search tree with an inorder traversal that stops early.Practice · medium · LeetCodeLowest common ancestor of a binary search treeFind the lowest node that has both p and q as descendants, by walking down from the root until the two keys split.

Asked in interviews

When would you use a binary search tree instead of a hash table?

Something wrong with this lesson? Report a problem