Binary Search Tree
A hierarchical data structure where each node has at most two children, with left child < parent < right child.
Ready to build tree
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Imagine a family tree where every parent has at most two children. In a BST, we organize numbers so that everything to the left is smaller and everything to the right is larger. This makes finding a number very fast—like looking up a word in a dictionary!
Concept
A Binary Search Tree (BST) is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree.
How it Works
- Root: The top node of the tree.
- Left Subtree: Contains values smaller than the root.
- Right Subtree: Contains values larger than the root.
- Leaf: A node with no children.
Step-by-Step Breakdown
- Start at the Root.
- If
Value < CurrentNode.Value, go Left. - If
Value > CurrentNode.Value, go Right. - If you reach an empty spot (NULL), insert the new node there.
When to Use
- Fast Lookup: Searching is O(log n) on average.
- Sorted Data: In-order traversal gives sorted elements.
- Dynamic Data: Efficient insertions and deletions compared to arrays.
When NOT to Use
- Unbalanced Trees: In worst case (skewed tree), operations become O(n).
- Constant Time Access: If you need O(1) access by index (use Array).
How to Identify
Look for problems involving searching, sorting, or maintaining a dynamic sorted set of elements. Keywords: "Binary Search", "Tree", "Hierarchy", "Sorted".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.