Binary Search Tree (BST)
Trees & GraphsOrdered hierarchical storage with monotonic inorder traversal
37 problems·9 Easy·25 Medium·3 Hard
Pattern Study Guide & Cheat Sheet▼
Exploit the BST invariant (every left descendant < root < every right descendant) to search, insert, and validate in O(height) time without inspecting the whole tree.
Core Invariant: BST Invariant: Validating a node requires verifying it against an ancestor range `(low, high)`, NOT just its immediate parent. Inorder traversal of a BST always yields strictly sorted ascending order.
Recognize it (Keywords & Signals)
- Validate Binary Search Tree
- Lowest Common Ancestor in BST
- Kth smallest / largest element in BST
- Convert sorted array / list to balanced BST
- Delete / Insert node in BST
When NOT to use
Tree does not follow BST ordering property or duplicates are allowed without clear convention.
How to solve (Step-by-step)
- 1.For validation: pass valid bounds `(low, high)` down the tree: `low < node.val < high`.
- 2.For search/LCA: compare `p.val` and `q.val` with `curr.val`. If both smaller, go left; if both larger, go right; if they split, `curr` IS the LCA!
- 3.For kth smallest: execute iterative inorder traversal using stack; the k-th popped node is the k-th smallest.
Watch for (Interview Traps)
- Only checking immediate parent: `node.left.val < node.val` allows invalid grand-ancestors (e.g. right child of left subtree > root)
- Handling `<` vs `<=`: LeetCode standard BST has strictly distinct values (`low < val < high`)
- Forgetting that BST operations degrade to O(N) if the tree is unbalanced
Validate BST (Range Invariant) & Inorder Traversal
def is_valid_bst(root: TreeNode | None) -> bool:
def validate(node: TreeNode | None, low: float, high: float) -> bool:
if not node:
return True
# Node value must strictly lie within inherited ancestor bounds
if not (low < node.val < high):
return False
# Left children must be < node.val; Right children must be > node.val
return (validate(node.left, low, node.val) and
validate(node.right, node.val, high))
return validate(root, float('-inf'), float('inf'))- Cost
- O(H) where H = height (O(log N) balanced, O(N) skewed) · O(H) stack depth (Inorder traversal yields sorted order in O(N) time.)
Canonical problems
#98 Validate Binary Search Tree: Verify ancestor bounds (low, high) on every node
#235 Lowest Common Ancestor of a BST: O(H) search: split point between p and q is the LCA
#230 Kth Smallest Element in a BST: Inorder traversal visits nodes in sorted order; stop at k
#108 Convert Sorted Array to Binary Search Tree: Pick middle element as root and recurse on halves
⌘K
Medium·23 companies·Max freq 88%·Acc 36.0%
WixNeetCode 150NeetCode 150+20
Medium·14 companies·Max freq 100%·Acc 70.9%
XXNeetCode 150+11
Medium·14 companies·Max freq 88%·Acc 77.0%
UberNeetCode 150NeetCode 150+11
Medium·10 companies·Max freq 100%·Acc 66.9%
ZenefitsLyftSalesforce+7
Easy·9 companies·Max freq 75%·Acc 75.8%
AirbnbAccentureAmazon+6
Medium·7 companies·Max freq 63%·Acc 73.5%
AndurilMicrosoftAmazon+4
Medium·6 companies·Max freq 100%·Acc 51.2%
Pocket GemsDocusignMicrosoft+3
Medium·6 companies·Max freq 38%·Acc 84.4%
AmazonSalesforceMeta+3
Medium·5 companies·Max freq 100%·Acc 51.8%
ZenefitsExpediaSalesforce+2
Medium·4 companies·Max freq 64%·Acc 65.6%
MetaTikTokAmazon+1
# | Problem | Difficulty | Top Companies↓ | Frequency | Acceptance | |
|---|---|---|---|---|---|---|
| #98 | Validate Binary Search Tree TreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 88% | 36.0% | ||
| #235 | Medium | 100% | 70.9% | |||
| #230 | Kth Smallest Element in a BST TreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 88% | 77.0% | ||
| #96 | Unique Binary Search Trees MathDynamic ProgrammingTreeBinary Search TreeBinary Tree | Medium | 88% | 63.9% | ||
| #450 | Delete Node in a BST TreeBinary Search TreeBinary Tree | Medium | 53% | 55.0% | ||
| #109 | Convert Sorted List to Binary Search Tree Linked ListDivide and ConquerTreeBinary Search TreeBinary Tree | Medium | 100% | 66.9% | ||
| #108 | Convert Sorted Array to Binary Search Tree ArrayDivide and ConquerTreeBinary Search TreeBinary Tree | Easy | 75% | 75.8% | ||
| #270 | Closest Binary Search Tree Value Binary SearchTreeDepth-First SearchBinary Search TreeBinary Tree | Easy | 88% | 49.2% | ||
| #653 | Two Sum IV - Input is a BST Hash TableTwo PointersTreeDepth-First SearchBreadth-First SearchBinary Search TreeBinary Tree | Easy | 88% | 63.5% | ||
| #173 | Binary Search Tree Iterator StackTreeDesignBinary Search TreeBinary TreeIterator | Medium | 63% | 76.7% | ||
| #701 | Insert into a Binary Search Tree TreeBinary Search TreeBinary Tree | Medium | 63% | 73.5% | ||
| #285 | Inorder Successor in BST TreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 100% | 51.2% | ||
| #938 | Range Sum of BST TreeDepth-First SearchBinary Search TreeBinary Tree | Easy | 78% | 87.6% | ||
| #1008 | Construct Binary Search Tree from Preorder Traversal ArrayStackTreeBinary Search TreeMonotonic StackBinary Tree | Medium | 38% | 84.4% | ||
| #700 | Search in a Binary Search Tree TreeBinary Search TreeBinary Tree | Easy | 25% | 82.9% | ||
| #255 | Verify Preorder Sequence in Binary Search Tree ArrayStackTreeBinary Search TreeRecursionMonotonic StackBinary Tree | Medium | 100% | 51.8% | ||
| #1382 | Balance a Binary Search Tree Divide and ConquerGreedyTreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 38% | 86.3% | ||
| #1373 | Maximum Sum BST in Binary Tree Dynamic ProgrammingTreeDepth-First SearchBinary Search TreeBinary TreeDP on Trees | Hard | 38% | 48.1% | ||
| #95 | Unique Binary Search Trees II Dynamic ProgrammingBacktrackingTreeBinary Search TreeBinary Tree | Medium | 28% | 62.8% | ||
| #783 | Minimum Distance Between BST Nodes TreeDepth-First SearchBreadth-First SearchBinary Search TreeBinary Tree | Easy | 88% | 61.6% | ||
| #449 | Serialize and Deserialize BST StringTreeDepth-First SearchBreadth-First SearchDesignBinary Search TreeBinary Tree | Medium | 68% | 59.8% | ||
| #426 | Convert Binary Search Tree to Sorted Doubly Linked List Linked ListStackTreeDepth-First SearchBinary Search TreeBinary TreeDoubly-Linked List | Medium | 64% | 65.6% | ||
| #669 | Trim a Binary Search Tree TreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 42% | 66.8% | ||
| #501 | Find Mode in Binary Search Tree TreeDepth-First SearchBinary Search TreeBinary Tree | Easy | 25% | 59.1% | ||
| #538 | Convert BST to Greater Tree TreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 25% | 71.8% | ||
| #510 | Inorder Successor in BST II TreeBinary Search TreeBinary Tree | Medium | 78% | 61.1% | ||
| #272 | Closest Binary Search Tree Value II Two PointersStackTreeDepth-First SearchBinary Search TreeHeap (Priority Queue)Binary Tree | Hard | 63% | 61.2% | ||
| #1038 | Binary Search Tree to Greater Sum Tree TreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 56% | 88.4% | ||
| #530 | Minimum Absolute Difference in BST TreeDepth-First SearchBreadth-First SearchBinary Search TreeBinary Tree | Easy | 29% | 59.5% | ||
| #1932 | Merge BSTs to Create Single BST ArrayHash TableTreeDepth-First SearchBinary Search TreeBinary Tree | Hard | 13% | 39.6% | ||
| #776 | Split BST TreeBinary Search TreeRecursionBinary Tree | Medium | 100% | 82.2% | ||
| #333 | Largest BST Subtree Dynamic ProgrammingTreeDepth-First SearchBinary Search TreeBinary TreeDP on Trees | Medium | 27% | 45.9% | ||
| #1305 | All Elements in Two Binary Search Trees TreeDepth-First SearchBinary Search TreeSortingBinary Tree | Medium | 25% | 80.3% | ||
| #897 | Increasing Order Search Tree StackTreeDepth-First SearchBinary Search TreeBinary Tree | Easy | 13% | 79.0% | ||
| #1586 | Binary Search Tree Iterator II StackTreeDesignBinary Search TreeBinary TreeIterator | Medium | 25% | 63.5% | ||
| #1214 | Two Sum BSTs Two PointersBinary SearchStackTreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 25% | 68.2% | ||
| #2476 | Closest Nodes Queries in a Binary Search Tree ArrayBinary SearchTreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 25% | 44.7% |
Showing 37 of 37 problems in Binary Search Tree (BST)Filtered: All Companies