Trees (BST, AVL, Red-Black)

// BST Implementation & Traversals
class TreeNode<T> {
  val: T;
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
  constructor(val: T) { this.val = val; }
}

// Inorder Traversal (sorted order for BST)
function inorder<T>(root: TreeNode<T> | null): T[] {
  if (!root) return [];
  return [...inorder(root.left), root.val, ...inorder(root.right)];
}

// BST Search — O(log n) average
function search<T>(root: TreeNode<T> | null, target: T): boolean {
  if (!root) return false;
  if (root.val === target) return true;
  return target < root.val 
    ? search(root.left, target) 
    : search(root.right, target);
}

// BST Insert — O(log n) average
function insert(root: TreeNode<number> | null, val: number): TreeNode<number> {
  if (!root) 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;
}

// Max depth of binary tree
function maxDepth<T>(root: TreeNode<T> | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// Lowest Common Ancestor in BST
function lcaBST(
  root: TreeNode<number> | null,
  p: number,
  q: number
): TreeNode<number> | null {
  if (!root) return null;
  if (p < root.val && q < root.val) return lcaBST(root.left, p, q);
  if (p > root.val && q > root.val) return lcaBST(root.right, p, q);
  return root; // split point = LCA
}

// Validate BST
function isValidBST(
  root: TreeNode<number> | null,
  min = -Infinity,
  max = Infinity
): boolean {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;
  return isValidBST(root.left, min, root.val) 
      && isValidBST(root.right, root.val, max);
}