What is a Binary Search Tree?

A Binary Search Tree (BST) is a tree where each node has at most two children, and there’s a special ordering rule: everything in the left subtree is smaller than the node, and everything in the right subtree is larger.

Think of it like organizing books on a shelf. Books with titles starting A-M go on the left, N-Z go on the right. Then you do the same for each section.

The Basic Idea

Here’s how data flows in a BST:

Why Use BSTs?

BSTs are useful because:

1. Fast Search: Find any value in O(log n) time on average
2. Ordered Data: Values are automatically sorted
3. Efficient Operations: Insert, delete, and search are all fast
4. Flexible: Easy to modify and extend

Compare this to an array. To find a value in an unsorted array, you might need to check every element. That’s O(n) time. With a BST, you eliminate half the possibilities at each step.

Visual Example

Try building a BST yourself. Insert some numbers and watch how they organize:

Start with 50, then try 30, 70, 20, 40, 60, 80. Notice how smaller numbers go left and larger numbers go right.

Key Properties

Every valid BST follows these rules:

1. Left child < Parent: All nodes in the left subtree have smaller values
2. Right child > Parent: All nodes in the right subtree have larger values
3. No duplicates: Typically, each value appears only once
4. Recursive structure: Each subtree is also a valid BST

These rules make searching predictable. You always know which direction to go.

Real-World Uses

BSTs show up in many places:

• Databases: Indexing for fast lookups
• File systems: Organizing directory structures
• Game engines: Spatial partitioning
• Networking: Routing tables
• Compilers: Symbol tables

Understanding BSTs helps you recognize when they’re the right tool for a problem.

What’s Next?

Now that you know what a BST is, let’s look at its structure in detail. We’ll see how nodes connect and what makes a tree valid.