Search in Binary Search Tree
Mahabharata — The BST Oracle — Finding Any Warrior in the Ordered Formation
BST में खोज — वाम या दक्षिण?। लक्ष्य छोटा — बाएं जाओ; बड़ा — दाएं जाओ॥
*Search in BST — left or right? Target smaller — go left; larger — go right.*
The Story
In a BST, find the node with a given value and return the subtree rooted there (or null if not found).
For BST `[4,2,7,1,3]`, val=2: return subtree `[2,1,3]`.
**BST property:** For every node: - All values in left subtree < node.val - All values in right subtree > node.val
**Recursive:** ```java public TreeNode searchBST(TreeNode root, int val) { if (root == null || root.val == val) return root; return val < root.val ? searchBST(root.left, val) // Go left (target is smaller) : searchBST(root.right, val); // Go right (target is larger) } ```
**Iterative (O(1) space):** ```java while (root != null && root.val != val) { root = val < root.val ? root.left : root.right; } return root; ```
Trace `[4,2,7,1,3]`, val=2: - root=4: 2<4 → go left - root=2: 2==2 → return node 2 (with subtree [2,1,3]) ✓
Trace val=5: - root=4: 5>4 → go right - root=7: 5<7 → go left - root=null → return null ✓
**This is the fundamental BST operation.** Every BST algorithm (insert, delete, validate, kth smallest) builds on this search pattern.
The DFS Full Search
DFS without using BST property — O(n) worst case. Wastes the BST's ordering.
TreeNode searchDFS(TreeNode root, int val) {
if (root == null) return null;
if (root.val == val) return root;
TreeNode left = searchDFS(root.left, val);
return left != null ? left : searchDFS(root.right, val);
}The BST Binary Decision Wisdom
public TreeNode searchBST(TreeNode root, int val) {
while (root != null && root.val != val) {
root = val < root.val ? root.left : root.right;
}
return root;
}Step-by-Step Walkthrough
BST=[2,1,3], val=1 2!=1: 1<2→go left→1. 1==1 → return node. ✅
Deep Insight
**O(h) vs O(n):** The BST property enables binary search on a tree, achieving O(h) per search instead of O(n) DFS. For a balanced BST, h=O(log n). For a skewed BST (like a linked list), h=O(n) worst case.
**Foundation for all BST operations:** - Insert: search for position, insert at null - Delete: find node, handle 0/1/2 children cases - Validate: check BST property via inorder or bounds - Kth smallest: inorder traversal - Floor/ceiling: modified search returning closest values
**BST vs Binary Search:** BST is the tree data structure implementing binary search. The iterative searchBST IS binary search applied to a tree structure.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Ignore BST property, full DFS |
| Optimal | O(h) | O(1) | h = height; O(log n) balanced, O(n) skewed |
Pattern Recognition
✅ BST search: use ordering property at each step ✅ val<root: go left; val>root: go right; val==root: found ✅ O(h) — exploits BST property ✅ Foundation of all BST operations **LeetCode Trigger Phrases:** → "search in a binary search tree" → BST lookup by value → Foundation for insert/delete/validate BST
Bhagavad Gita 10.15
एकः स्वयमात्मानमात्मना वेत्ति तत्त्वतः।
One alone knows the Self through the Self in truth.
Connection: The BST knows where to find any value through its own internal structure — no external guide needed. At each node, the BST's own ordering property tells it: 'go left for smaller, right for larger.' Like the Self knowing the Self directly without external mediation, the BST finds any value through direct structural knowledge — the binary decision at each level guided purely by the inherent ordering of values within the tree.