Core Concept Mastery • DSA Module
BST search uses the ordering property to eliminate half the remaining nodes at each step. Starting at the root, compare the target value: if less, go left; if greater, go right; if equal, found. This achieves O(log n) average time complexity.
Finding a word in a dictionary: You don't start at page 1. You open to the middle. If your word comes before the middle word, you search the first half. If after, you search the second half. You repeat this binary division until you find the word. This is exactly how BST search works — divide and conquer.
We don't need to check every node. We can eliminate half the tree at every step!
1. Compare target with root
2. If target < root → search LEFT
3. If target > root → search RIGHT
4. If target == root → FOUND!
5. If reach NULL → NOT FOUND
Check every element
O(n) time
Eliminate half at each step
O(log n) average
For 1M elements: Linear = 1M comparisons, BST = ~20 comparisons!
1Node* search(Node* root, int target) {2if (root == NULL || root->data == target)3return root;4if (target < root->data)6return search(root->left, target); // Go left7else8return search(root->right, target); // Go right9}
The Binary Search Algorithm
How It Works
1. Start at the root
2. Compare target value with current node
3. If target == current node → Found! Return node
4. If target < current node → Search left subtree (all values there are smaller)
5. If target > current node → Search right subtree (all values there are larger)
6. If you reach NULL → Not found, return NULL
Why It's Fast
At each step, you eliminate half the remaining nodes:
This is O(log n) — logarithmic time complexity.
Recursive Implementation
Node* search(Node* root, int target) {
if (root == NULL || root->data == target)
return root;
if (target < root->data)
return search(root->left, target); // Search left
else
return search(root->right, target); // Search right
}
Iterative Implementation
Node* search(Node* root, int target) {
while (root != NULL && root->data != target) {
if (target < root->data)
root = root->left;
else
root = root->right;
}
return root;
}
Time Complexity
Space Complexity
Comparison with Linear Search
For n = 1,000,000 elements:
That's 50,000x faster in worst case!
BST search is dramatically faster than linear search. Instead of checking every element O(n), you eliminate half the tree at each step O(log n). For 1 million elements, linear search needs up to 1 million comparisons; BST search needs at most 20 comparisons. This is why BSTs power database indexes and symbol tables.
"What is the time complexity of searching in a Binary Search Tree, and why?"
Average case is O(log n) because at each step, you eliminate half the remaining nodes by comparing with the root and going left or right. Worst case is O(n) if the tree is skewed (degenerates to a linked list). The logarithmic complexity comes from the binary division at each level.