20. Binary Search Trees
Insert, delete, validate, kth smallest and BST iterators.
🎬 Episodes 61–63: video coming soon
Your progress0 of 12
4easy
8medium
0hard
Understand the topic
A binary search tree keeps everything smaller on the left and everything bigger on the right, at every node. So you can search by going one way, like binary search on a tree: O(h), where h is the height.
Two facts solve most BST problems. An inorder traversal visits the values in sorted order. And you can pass an allowed range (min, max) down the tree.
| # | Problem | Pattern | Level | ||
|---|---|---|---|---|---|
| 1 | Search in a Binary Search Tree #700 | BST walk | Easy | LeetCode ↗ | |
| 2 | Convert Sorted Array to Binary Search Tree #108 | Middle as root | Easy | LeetCode ↗ | |
| 3 | Minimum Absolute Difference in BST #530 | Inorder = sorted | Easy | LeetCode ↗ | |
| 4 | Range Sum of BST #938 | Pruned DFS | Easy | LeetCode ↗ | |
| 5 | Insert into a Binary Search Tree #701 | BST walk to a null slot | Medium | LeetCode ↗ | |
| 6 | Delete Node in a BST #450 | Three deletion cases | Medium | LeetCode ↗ | |
| 7 | Validate Binary Search Tree #98 | Bounds passed down | Medium | LeetCode ↗ | |
| 8 | Kth Smallest Element in a BST #230 | Inorder with a counter | Medium | LeetCode ↗ | |
| 9 | Lowest Common Ancestor of a Binary Search Tree #235 | Split point | Medium | LeetCode ↗ | |
| 10 | Binary Search Tree Iterator #173 | Controlled inorder with a stack | Medium | LeetCode ↗ | |
| 11 | Construct Binary Search Tree from Preorder Traversal #1008 | Upper-bound recursion | Medium | LeetCode ↗ | |
| 12 | Recover Binary Search Tree #99 | Inorder to find swapped pair | Medium | LeetCode ↗ |
Nothing matches that filter.
Work top to bottom — each list goes from easy to hard. Try a problem for at least 15 minutes before opening a hint. Ticks are saved in your browser.