HomeBinary Search Trees
Binary Search Trees
Ordered trees — left is smaller, right is larger, search in O(h).
21 shown
- OverviewThe BST ordering propertyanimatedEasy
- Insert into a BSTWalk down, hang a new leafanimatedMedium
- Validate BSTEvery node within a (min, max) rangeanimatedMedium
- Kth Smallest in a BSTInorder visits keys in sorted orderanimatedMedium
- Lowest Common Ancestor in a BSTThe split point of the two valuesanimatedMedium
- Practice problems
- Introduction to BSTLeft is smaller, right is bigger — everywhereanimatedEasy
- Search in a Binary Search TreeCompare and descendanimatedEasy
- Find Min/Max in BSTWalk hard left, or hard rightEasy
- Floor and Ceil in a BSTRecord the candidate as you descendEasy
- Floor in a Binary Search TreeLargest value not above the keyEasy
- Insert a given node in BSTDescend to the empty spot and attachanimatedMedium
- Delete a node in BSTThree cases; two children is the interesting oneMedium
- Kth Smallest and Largest element in BSTIn-order traversal, countinganimatedMedium
- Check if a tree is a BST or notCarry a valid range down, not just the parentanimatedMedium
- LCA in BSTDescend until the values splitanimatedMedium
- Construct a BST from a preorder traversalBuild with an upper boundMedium
- Inorder Successor/Predecessor in BSTRemember the last turn you tookMedium
- Merge 2 BST'sTwo in-order traversals, then mergeHard
- Two Sum In BSTTwo iterators, walking inwardsHard
- Correct BST with two nodes swappedIn-order finds exactly the two anomaliesHard
- Largest BST in Binary TreeReturn (min, max, size, isBST) from each subtreeHard