Binary Search Tree

Basic Concepts

Node Structure

Each node stores a value and pointers to left and right children. By convention, left subtree contains smaller values, right subtree contains larger values.

Properties

• Left subtree: values < current node.
• Right subtree: values > current node.
• Duplicates: usually avoided; if allowed, define a consistent policy (e.g. duplicates go to right).

Operations

Insertion

1. Start at the root.
2. Compare value, move left if smaller, right if larger.
3. Insert at the null child position.

Deletion

Three cases: leaf node, node with one child, node with two children (replace with in-order successor or predecessor).

Search

1. Start at root and compare.
2. Follow left/right until found or null.

Traversals

• In-order: left, root, right — yields sorted order.
• Pre-order: root, left, right — useful to copy the tree.
• Post-order: left, right, root — useful for deleting a tree.
• Level-order: BFS using a queue.

public TreeNode searchBST(TreeNode root, int val) {
  while (root != null) {
    if (val == root.val) return root;
    root = val < root.val ? root.left : root.right;
  }
  return null;
}