The Binary Search Tree (BST) – The Organized Tree

Welcome to Module 3! In the last section, we successfully built a basic Binary Tree in Java. That was a huge step, but the real power of trees comes from the special properties we can enforce on them. Not all trees are created equal; different structures are optimized for different tasks.

In this module, we'll go on a tour of the most important tree types you'll encounter. Understanding these variations is crucial for choosing the right data structure for a problem and for acing your coding interviews.

1. The Binary Search Tree (BST) – The Organized Tree

The Binary Search Tree (BST) is arguably the most famous type of tree. Its power comes from one simple, elegant rule that it must obey at all times.

The BST Property (or Invariant): For any given node N:

1. All values in N's left subtree must be less than N's value.
2. All values in N's right subtree must be greater than N's value.
3. Both the left and right subtrees must also be binary search trees.

Notice how everything to the left of 8 is smaller, and everything to the right is larger. This rule applies all the way down!

Why is this so important? This ordering makes searching for an element incredibly fast. Instead of checking every node, you can discard half of the tree at every step. This leads to a search time of O(log n) on average, which is a massive performance gain over the O(n) search time in an array or list.

2. Structural Purity – Full vs. Complete Binary Trees

Next, let's look at two types of trees defined by their shape and structure, not the values they hold.

The Full Binary Tree

A Full Binary Tree (sometimes called a proper or strict binary tree) is a tree where every node has either zero or two children. There are no nodes with only one child.

This structure is simple and predictable, often used in applications where decisions are strictly binary.

The Complete Binary Tree

A Complete Binary Tree is a bit different. In this tree, every level is completely filled, except possibly for the last level, which is filled from left to right.

This is a complete tree. If node F were a child of C on the right, it would not be complete because the last level wouldn't be filled from the left.

Why care about this? The complete binary tree's structure is essential because it's the foundation for another famous data structure: the Heap, which is often used to implement Priority Queues.

3. The Quest for Balance – Balanced Binary Trees

Let's go back to our amazing BST. It's fast, right? Well... usually. What happens if you insert numbers into a BST in sorted order (1, 2, 3, 4, 5)? You get this:

This is a "degenerate" or "skewed" tree. It's basically a linked list! Searching this tree is now slow, back to O(n). We've lost our advantage.

The solution is the Balanced Binary Tree. This is a type of BST that automatically performs rotations and adjustments during insertions and deletions to ensure the tree never gets too skewed. It maintains a low height, guaranteeing that operations like search, insert, and delete remain at a speedy O(log n) in the worst case.

Famous examples include AVL Trees and Red-Black Trees. You don't need to know how to implement them from scratch just yet, but you must understand why they exist: to prevent the worst-case scenario in a BST and guarantee high performance. In fact, built-in data structures like Java's TreeMap are often implemented using these self-balancing trees.