The Power of Order

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

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

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

1. Complexity

  • Search: O(log N) average. O(N) worst case (skewed tree).
  • Insert: O(log N) average.
  • Delete: O(log N) average.

2. Staff Level Depth: The Balance Problem

What happens if we insert numbers in order: 1, 2, 3, 4, 5?

  • 1 is root.
  • 2 is right of 1.
  • 3 is right of 2…
  • The Result: A “Stick” (Skewed Tree).

A skewed tree is just a Linked List in disguise. Our O(\log N) search just became O(N).

The Conceptual Fix: Rotations

To stay “hero” level, you must understand that self-balancing trees (like AVL or Red-Black) solve this by Rotating nodes.

  • If the right side is too heavy, we “pull” the right child up to be the new parent.
  • This maintains the BST Property while reducing Height.

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

Tree Empty.

4. Recursive Implementation

Java

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;
}

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

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
}

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)
}