Binary Trees & BSTs

Introduction: Entering the Hierarchy

So far, every structure we have discussed (Arrays, Lists, Stacks, Queues) has been linear—items arranged in a straight line, one after another.

However, real-world data is often hierarchical: file systems, HTML DOMs, organizational charts, and decision processes. To model this, we use Trees.

The most fundamental tree structure in computer science is the Binary Tree. A Binary Tree is a structure where every node has at most two children: a Left child and a Right child.

The Mechanics

1. The Binary Tree

A standard Binary Tree has no strict rules about where data goes. It is simply a structural shape.

• Root: The top-most node.

• Leaf: A node with no children.

• Edge: The link between two nodes.

2. The Binary Search Tree (BST)

The BST is where the magic happens. It enforces a strict logical rule that allows for rapid searching:

• Rule: For any given node, all values in the Left Subtree are smaller, and all values in the Right Subtree are larger.

This rule means that every decision you make (go left or go right) eliminates half of the remaining data. This is the origin of logarithmic time complexity.

Operations & Complexity Analysis

Complexity depends entirely on the Shape (Height) of the tree.

Operation	Average (Balanced)	Worst Case (Skewed)	Notes
Search	O(\log n)	O(n)	In a balanced tree, you traverse the height (h = \log n). In a line, it behaves like a Linked List.
Insertion	O(\log n)	O(n)	You must trace the path from Root to a Leaf to find the empty spot.
Deletion	O(\log n)	O(n)	Finding the node is O(\log n). Re-wiring is constant, unless the node has two children (requires finding a successor).

JavaScript Implementation

We implement Trees using a Node class, similar to a Linked List, but with two pointers instead of one.

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    // Insert: O(log n)
    insert(value) {
        const newNode = new Node(value);
        if (!this.root) {
            this.root = newNode;
            return this;
        }
        
        let current = this.root;
        while (true) {
            if (value === current.value) return undefined; // No duplicates
            
            if (value < current.value) {
                // Go Left
                if (!current.left) {
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                // Go Right
                if (!current.right) {
                    current.right = newNode;
                    return this;
                }
                current = current.right;
            }
        }
    }

    // Search: O(log n)
    contains(value) {
        if (!this.root) return false;
        
        let current = this.root;
        while (current) {
            if (value === current.value) return true;
            
            if (value < current.value) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return false;
    }

    // DFS Traversal (In-Order): Prints sorted values
    // Complexity: O(n) - visits every node
    printInOrder(node = this.root) {
        if (node) {
            this.printInOrder(node.left);
            console.log(node.value);
            this.printInOrder(node.right);
        }
    }
}

// Usage
const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(5);
tree.insert(13);
tree.insert(2);
tree.insert(7);

// Structure created:
//       10
//      /  \
//     5    13
//    / \
//   2   7

console.log(tree.contains(7)); // true
tree.printInOrder(); // Output: 2, 5, 7, 10, 13 (Sorted!)

Expert Insight: The "Balance" Trap

The most critical concept in Tree theory is Balance.

1. The Best Case: O(\log n)

If you insert data in a random order (e.g., 10, 5, 15), the tree grows "wide". The height is kept minimal. With 1,000,000 nodes, a balanced tree is only ~20 levels deep. You can find any item in 20 comparisons.

2. The Worst Case: O(n)

If you insert sorted data (e.g., 1, 2, 3, 4, 5), the tree never branches to the left. It grows in a straight line to the right.

Structurally, this is no longer a Tree; it is a Linked List. Searching it takes O(n) time.

The Solution: Self-Balancing Trees

In production databases (like PostgreSQL indices or Java's TreeMap), we never use a raw BST. We use AVL Trees or Red-Black Trees. These algorithms automatically rotate nodes during insertion to ensure the tree remains short and fat, guaranteeing O(\log n) performance.

3. Depth First Search (DFS) vs Breadth First Search (BFS)

• DFS (Stack/Recursion): Goes deep to a leaf before backtracking. Used for mazes, pre-order/in-order analysis.

• BFS (Queue): Scans level-by-level. Used for finding the "shortest path" or networking (peer-to-peer).

Conclusion

Binary Search Trees are the theoretical grandfather of efficient searching.

1. Use BSTs when you need to keep data Sorted and searchable.

2. Beware of inserting sorted data into a basic BST (it degrades to a Linked List).

3. Remember that "Tree Traversal" (visiting every node) is always O(n), but "Search" (finding one node) should be O(\log n).