Core Concept Mastery • DSA Module
A Binary Search Tree (BST) is a binary tree where for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater than the node's value. This ordering property enables efficient searching.
Think of a phone book organized as a BST. Names starting with A-M go left, N-Z go right. Within A-M, A-G go left, H-M go right. This binary division continues, allowing you to find any name in O(log n) steps instead of scanning all pages.
A special Binary Tree optimized for Searching.
This property holds recursively for every node
Inorder Traversal of a BST gives a Sorted Array!
Left → Root → Right with Left < Root < Right = Sorted order
• At most 2 children
• No ordering constraint
Search: O(n)
• At most 2 children
• Left < Root < Right
Search: O(log n) average
1. Compare target with root
2. If target < root → search LEFT (eliminate right half)
3. If target > root → search RIGHT (eliminate left half)
4. Repeat until found or NULL
Result: O(log n) search time!
The Ordering Property
What Makes It a BST?
A Binary Search Tree is a binary tree with a special ordering property:
The Golden Rule
For any node with value X:
Why It Works
The ordering property enables binary search:
1. Compare target with root
2. If target < root, search left subtree (eliminate right half)
3. If target > root, search right subtree (eliminate left half)
4. Repeat until found or reach NULL
At each step, you eliminate half the remaining nodes — that's O(log n)!
BST vs Regular Binary Tree
The Magic Property
Inorder traversal of a BST always gives sorted (ascending) order!
Why? Because Inorder visits Left → Root → Right. With Left < Root < Right property, smaller values come before larger values — exactly sorted order.
BST Operations
When BST Degrades
If elements are inserted in sorted order (1, 2, 3, 4, 5...), the BST becomes a skewed tree (linked list), and operations become O(n). This is why balanced BSTs (AVL, Red-Black) exist.
BSTs enable O(log n) average-case searching, insertion, and deletion — much faster than O(n) linear search in arrays or linked lists. They're used in database indexing, symbol tables, priority queues, and anywhere you need fast lookups on dynamic data.
"What property distinguishes a Binary Search Tree from a regular Binary Tree?"
A Binary Search Tree has an ordering property: for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater than the node's value. A regular binary tree has no such ordering constraint — it only requires 'at most 2 children'.