Ordered hierarchical storage with monotonic inorder traversal
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.
Tree does not follow BST ordering property or duplicates are allowed without clear convention.
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'))# | Problem | Difficulty | Top Companies↓ | Frequency | Acceptance | |
|---|---|---|---|---|---|---|
| #98 | Validate Binary Search Tree TreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 88% | 0.4% | ||
| #235 | Lowest Common Ancestor of a Binary Search Tree TreeDepth-First SearchBinary Search TreeBinary TreeBinary LiftingLowest Common Ancestor | Medium | 100% | 0.7% | ||
| #230 | Kth Smallest Element in a BST TreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 88% | 77.0% | ||
| #703 | Kth Largest Element in a Stream TreeDesignBinary Search TreeHeap (Priority Queue)Binary TreeData Stream | Easy | 93% | 61.3% | ||
| #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 | 55% | 55.0% | ||
| #109 | Convert Sorted List to Binary Search Tree Linked ListDivide and ConquerTreeBinary Search TreeBinary Tree | Medium | 100% | 66.9% | ||
| #270 | Closest Binary Search Tree Value Binary SearchTreeDepth-First SearchBinary Search TreeBinary Tree | Easy | 88% | 49.2% | ||
| #108 | Convert Sorted Array to Binary Search Tree ArrayDivide and ConquerTreeBinary Search TreeBinary Tree | Easy | 75% | 75.8% | ||
| #173 | Binary Search Tree Iterator StackTreeDesignBinary Search TreeBinary TreeIterator | Medium | 63% | 76.7% | ||
| #99 | Recover Binary Search Tree TreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 53% | 60.2% | ||
| #701 | Insert into a Binary Search Tree TreeBinary Search TreeBinary Tree | Medium | 63% | 73.5% | ||
| #1008 | Construct Binary Search Tree from Preorder Traversal ArrayStackTreeBinary Search TreeMonotonic StackBinary Tree | Medium | 43% | 84.4% | ||
| #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% | ||
| #700 | Search in a Binary Search Tree TreeBinary Search TreeBinary Tree | Easy | 27% | 82.9% | ||
| #255 | Verify Preorder Sequence in Binary Search Tree ArrayStackTreeBinary Search TreeRecursionMonotonic StackBinary Tree | Medium | 100% | 51.8% | ||
| #1373 | Maximum Sum BST in Binary Tree Dynamic ProgrammingTreeDepth-First SearchBinary Search TreeBinary TreeDP on Trees | Hard | 38% | 48.1% | ||
| #1382 | Balance a Binary Search Tree Divide and ConquerGreedyTreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 38% | 86.3% | ||
| #95 | Unique Binary Search Trees II Dynamic ProgrammingBacktrackingTreeBinary Search TreeBinary Tree | Medium | 31% | 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 | 69% | 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% | ||
| #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% | ||
| #669 | Trim a Binary Search Tree TreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 44% | 66.8% | ||
| #501 | Find Mode in Binary Search Tree TreeDepth-First SearchBinary Search TreeBinary Tree | Easy | 26% | 59.1% | ||
| #538 | Convert BST to Greater Tree TreeDepth-First SearchBinary Search TreeBinary Tree | Medium | 25% | 71.8% | ||
| #776 | Split BST TreeBinary Search TreeRecursionBinary Tree | Medium | 100% | 82.2% | ||
| #510 | Inorder Successor in BST II TreeBinary Search TreeBinary Tree | Medium | 84% | 61.1% | ||
| #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% | ||
| #333 | Largest BST Subtree Dynamic ProgrammingTreeDepth-First SearchBinary Search TreeBinary TreeDP on Trees | Medium | 28% | 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% |
Browse company-specific interview problem lists and recency breakdowns:
Master core algorithmic patterns tested in FAANG & Big Tech coding interviews.
Ordered hierarchical storage with monotonic inorder traversal It is categorized under Trees & Graphs and features 38 curated interview problems across Easy (9), Medium (26), and Hard (3) difficulties.
Companies frequently asking Binary Search Tree (BST) questions include Amazon, Google, Meta, Microsoft, Bloomberg, NeetCode 150.
Start by studying the algorithmic strategy and template code, then practice Easy and Medium problems before attempting Hard problems under timed conditions.