A Binary Search Tree is a specialized binary tree with a Ordering Property:

• Every node in the Left Subtree is smaller than the root.
• Every node in the Right Subtree is larger than the root.

Think of an Organized Filing Cabinet:

1. You're looking for file #42.
2. The root folder is #50.
3. Since $42 < 50$, you know for a FACT that #42 is in the left drawer.
4. You don't even have to look at the right drawer!
5. This makes searching incredibly fast.

---

Complexity Analysis (Balanced)

• Search: $O(\log n)$
• Insert: $O(\log n)$
• Delete: $O(\log n)$

The "Skewed" Danger

If you insert data in sorted order (e.g., 1, 2, 3, 4), the BST becomes a Linked List. All complexities degrade to $O(n)$. This is why balanced trees (AVL, Red-Black) were invented.

---

javascript Standard
/**
 * Search in BST
 */
function searchBST(root, val) {
  if (!root || root.val === val) return root;

  if (val < root.val) {
    return searchBST(root.left, val);
  } else {
    return searchBST(root.right, val);
  }
}

/**
 * Insert into BST
 */
function insertIntoBST(root, val) {
  if (!root) return new TreeNode(val);

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

---

Deletion Logic (The Hard Part)

Deleting a node with 2 children is tricky. The Trick: Find the In-order Successor (smallest node in the right subtree), replace the target node's value with it, and then delete the successor.

Top Questions

• Validate if a tree is a BST (Don't just check immediate children; all left nodes must be smaller than the ancestor!).
• Convert a Sorted Array to a Balanced BST.
• K-th smallest element in a BST (Perform in-order traversal and stop at K).
• Lowest Common Ancestor (LCA) in a BST.