The Power of Order

[!NOTE] This module explores the core principles of Binary Search Trees (BST), deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

A Binary Search Tree (BST) is a Binary Tree with a strict rule:

Left Child < Parent
Right Child > Parent
No Duplicates (usually).

This structure allows us to discard half the tree at every step when searching. It’s like Binary Search, but dynamic.

The Balance Problem

If we insert numbers in order (1, 2, 3, 4, 5), the tree becomes a “Stick” (skewed), degrading to a Linked List with O(N) complexity. Self-balancing trees (AVL, Red-Black) solve this via rotations.

2. Interactive Analysis

Watch the path. Notice how we only go Left or Right, never both.

Tree Empty.

3. Implementation

Java

```java
// Recursive Insert
public TreeNode insert(TreeNode root, int val) {
  if (root == null) return new TreeNode(val);

  if (val < root.val) {
    root.left = insert(root.left, val);
  } else if (val > root.val) {
    root.right = insert(root.right, val);
  }
  return root;
}

// Recursive Search
public TreeNode search(TreeNode root, int val) {
  if (root == null || root.val == val) return root;

  if (val < root.val) return search(root.left, val);
  return search(root.right, val);
}
```

```go
// Recursive Insert
func Insert(root *TreeNode, val int) *TreeNode {
  if root == nil {
    return &TreeNode{Val: val}
  }
  if val < root.Val {
    root.Left = Insert(root.Left, val)
  } else if val > root.Val {
    root.Right = Insert(root.Right, val)
  }
  return root
}

// Recursive Search
func Search(root *TreeNode, val int) *TreeNode {
  if root == nil || root.Val == val {
    return root
  }
  if val < root.Val {
    return Search(root.Left, val)
  }
  return Search(root.Right, val)
}
```

4. Complexity Analysis

Operation	Time (Avg)	Time (Worst)	Space (Avg)	Notes
Search	O(log N)	O(N)	O(log N)	Worst case is a linked list (skewed).
Insert	O(log N)	O(N)	O(log N)	Same as search.
Delete	O(log N)	O(N)	O(log N)	Requires pointer manipulation.