← All patternsBST Ordering · template
Pattern · Trees
BST Ordering
Use left < node < right to skip half the tree, and in-order traversal to visit values in sorted order.
Time O(h) for search, O(n) for full checks · Space O(h)
Taught in Module 17: Binary Search Trees
Think of it like this
A library sorted by call number: you know which aisle to skip without looking inside.
Clues that point here
- → Binary search tree input
- → Kth smallest
- → Validate a BST
- → Search, insert or delete by value
Not this pattern when
- ✕ The tree is a plain binary tree with no ordering
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
boolean valid(TreeNode node, long low, long high) {
if (node == null) return true;
if (node.val <= low || node.val >= high) return false;
return valid(node.left, low, node.val) && valid(node.right, node.val, high);
}
// call: valid(root, Long.MIN_VALUE, Long.MAX_VALUE)Common versions
- Validate BST
- Kth smallest element
- LCA of a BST
- Insert into BST
- Convert sorted array to BST
Practice problems with this pattern
17.1Search in a Binary Search TreeEasymain pattern17.2Insert into a Binary Search TreeMediummain pattern17.3Validate Binary Search TreeMediummain pattern17.4Kth Smallest Element in a BSTMediummain pattern17.5Lowest Common Ancestor of a BSTMediummain pattern17.6Convert Sorted Array to BSTEasymain pattern17.7Two Sum in a BSTEasymain pattern17.8Delete Node in a BSTMediummain pattern17.9BST IteratorMediummain pattern