BST (Binary Search Tree)（二元搜尋樹）

# python
# IDEA: change the node, then recurse into both children; no ordering is used
# time = O(n), space = O(h)
def add_one(root):
    if not root:
        return
    root.val += 1
    add_one(root.left)
    add_one(root.right)

// java
// IDEA: change the node, then recurse into both children
// time = O(n), space = O(h)
void addOne(TreeNode root) {
    if (root == null) {
        return;
    }
    root.val += 1;
    addOne(root.left);
    addOne(root.right);
}

# python
# LC 700 - Search in a Binary Search Tree
# IDEA: compare, then step to the ONE child that can still hold val
# time = O(h), space = O(1)
def searchBST(root, val):
    node = root
    while node and node.val != val:
        node = node.left if val < node.val else node.right
    return node            # the matching node, or None when the walk falls off

// java
// LC 700 - Search in a Binary Search Tree
// IDEA: compare, then step to the ONE child that can still hold val
// time = O(h), space = O(1)
public TreeNode searchBST(TreeNode root, int val) {
    TreeNode node = root;
    while (node != null && node.val != val) {
        node = (val < node.val) ? node.left : node.right;
    }
    return node;
}

# python
# LC 701 - Insert into a Binary Search Tree
# IDEA: search for val; the null you fall off is where the new leaf goes
# time = O(h), space = O(h)
def insertIntoBST(root, val):
    if not root:
        return TreeNode(val)              # the empty spot: the new leaf
    if val < root.val:
        root.left = insertIntoBST(root.left, val)
    else:
        root.right = insertIntoBST(root.right, val)
    return root                           # unchanged nodes return themselves

// java
// LC 701 - Insert into a Binary Search Tree
// IDEA: search for val; the null you fall off is where the new leaf goes
// time = O(h), space = O(h)
public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }
    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
    return root;
}

# python
# LC 450 - Delete Node in a BST
# IDEA: find key; 0/1 child -> return the other child; 2 children -> copy the
#       right subtree's minimum in, then delete that minimum from the right subtree
# time = O(h), space = O(h)
def deleteNode(root, key):
    if not root:
        return None                       # key not in the tree
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left:                 # 0 children, or only a right child
            return root.right
        if not root.right:                # only a left child
            return root.left
        succ = root.right                 # 2 children: in-order successor
        while succ.left:
            succ = succ.left
        root.val = succ.val
        root.right = deleteNode(root.right, succ.val)
    return root

// java
// LC 450 - Delete Node in a BST
// IDEA: 0/1 child -> splice in the other child; 2 children -> successor swap
// time = O(h), space = O(h)
public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return null;
    }
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        if (root.left == null) {
            return root.right;
        }
        if (root.right == null) {
            return root.left;
        }
        TreeNode succ = root.right;
        while (succ.left != null) {
            succ = succ.left;
        }
        root.val = succ.val;
        root.right = deleteNode(root.right, succ.val);
    }
    return root;
}

[5,3,6,2,4,null,7], key = 3
at 5: 3 < 5  -> recurse left
at 3: found, two children (2, 4)
      successor = min of right subtree = 4
      copy 4 into this node, delete 4 from its right subtree (a leaf -> None)
result: [5,4,6,2,null,null,7]

# python
# LC 669 - Trim a Binary Search Tree
# IDEA: out-of-range root -> return the trimmed side that can still hold valid values;
#       in-range root -> keep it, trim and reattach both children
# time = O(n), space = O(h)
def trimBST(root, low, high):
    if not root:
        return None
    if root.val < low:                    # root and its left subtree are all too small
        return trimBST(root.right, low, high)
    if root.val > high:                   # root and its right subtree are all too large
        return trimBST(root.left, low, high)
    root.left = trimBST(root.left, low, high)
    root.right = trimBST(root.right, low, high)
    return root

// java
// LC 669 - Trim a Binary Search Tree
// IDEA: out-of-range root -> promote the trimmed side; in-range -> trim both children
// time = O(n), space = O(h)
public TreeNode trimBST(TreeNode root, int low, int high) {
    if (root == null) {
        return null;
    }
    if (root.val < low) {
        return trimBST(root.right, low, high);
    }
    if (root.val > high) {
        return trimBST(root.left, low, high);
    }
    root.left = trimBST(root.left, low, high);
    root.right = trimBST(root.right, low, high);
    return root;
}

low = 1, high = 3

        3                 3
       / \               /
      0   4    trim →   2
       \               /
        2             1
       /
      1

  - 3 in range        -> keep, trim both children
  - 0 < low           -> drop 0 and its (empty) left, return trim(right) = 2
  - 2 in range        -> keep; 1 in range -> keep (leaf)
  - 4 > high          -> drop 4 and its (empty) right, return trim(left) = None

# python
# LC 98 - Validate Binary Search Tree
# IDEA: carry the (low, high) interval down; None means "no bound on this side"
# time = O(n), space = O(h)
def isValidBST(root):
    def valid(node, low, high):
        if not node:
            return True
        if (low is not None and node.val <= low) or (high is not None and node.val >= high):
            return False
        return valid(node.left, low, node.val) and valid(node.right, node.val, high)
    return valid(root, None, None)

// java
// LC 98 - Validate Binary Search Tree
// IDEA: carry the (low, high) interval down; null means "no bound", so MIN_VALUE stays legal
// time = O(n), space = O(h)
public boolean isValidBST(TreeNode root) {
    return valid(root, null, null);
}

private boolean valid(TreeNode node, Integer low, Integer high) {
    if (node == null) {
        return true;
    }
    if ((low != null && node.val <= low) || (high != null && node.val >= high)) {
        return false;
    }
    return valid(node.left, low, node.val) && valid(node.right, node.val, high);
}

# python
# LC 98 - Validate Binary Search Tree (iterative)
# IDEA: BFS of (node, low, high); each child inherits the interval, tightened by its parent
# time = O(n), space = O(w)   w = the widest level
from collections import deque

def isValidBST(root):
    queue = deque([(root, None, None)])
    while queue:
        node, low, high = queue.popleft()
        if not node:
            continue
        if (low is not None and node.val <= low) or (high is not None and node.val >= high):
            return False
        queue.append((node.left, low, node.val))      # left: values below node.val
        queue.append((node.right, node.val, high))    # right: values above node.val
    return True

# python
# LC 230 - Kth Smallest Element in a BST
# IDEA: iterative in-order; the kth node popped is the kth smallest
# time = O(h + k), space = O(h)
def kthSmallest(root, k):
    stack = []
    node = root
    while node or stack:
        while node:                       # push the whole left spine
            stack.append(node)
            node = node.left
        node = stack.pop()                # the next value in sorted order
        k -= 1
        if k == 0:
            return node.val
        node = node.right                 # then the right subtree, in order
    return -1                             # k > number of nodes

// java
// LC 230 - Kth Smallest Element in a BST
// IDEA: iterative in-order; stop at the kth pop
// time = O(h + k), space = O(h)
public int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        k--;
        if (k == 0) {
            return node.val;
        }
        node = node.right;
    }
    return -1;
}

# python
# LC 108 - Convert Sorted Array to Binary Search Tree
# IDEA: the middle of the index range is the root; recurse on the two halves (no slicing)
# time = O(n), space = O(log n)
def sortedArrayToBST(nums):
    def build_range(left, right):
        if left > right:
            return None
        mid = (left + right) // 2
        root = TreeNode(nums[mid])
        root.left = build_range(left, mid - 1)
        root.right = build_range(mid + 1, right)
        return root
    return build_range(0, len(nums) - 1)

// java
// LC 108 - Convert Sorted Array to Binary Search Tree
// IDEA: the middle of the index range is the root; recurse on the two halves
// time = O(n), space = O(log n)
public TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}

private TreeNode build(int[] nums, int left, int right) {
    if (left > right) {
        return null;
    }
    int mid = left + (right - left) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = build(nums, left, mid - 1);
    root.right = build(nums, mid + 1, right);
    return root;
}

# python
# LC 235 - Lowest Common Ancestor of a Binary Search Tree
# IDEA: walk down while p and q sit on the SAME side; the first split point is the LCA
# time = O(h), space = O(1)
def lowestCommonAncestor(root, p, q):
    node = root
    while node:
        if p.val < node.val and q.val < node.val:
            node = node.left
        elif p.val > node.val and q.val > node.val:
            node = node.right
        else:
            return node                   # split here, or node is p or q
    return None

// java
// LC 235 - Lowest Common Ancestor of a Binary Search Tree
// IDEA: walk down while p and q sit on the SAME side; the first split point is the LCA
// time = O(h), space = O(1)
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode node = root;
    while (node != null) {
        if (p.val < node.val && q.val < node.val) {
            node = node.left;
        } else if (p.val > node.val && q.val > node.val) {
            node = node.right;
        } else {
            return node;
        }
    }
    return null;
}

[6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
node 6: 2 < 6 and 4 < 6   -> go left
node 2: 2 is not < 2       -> split (node is p) -> LCA = 2

BST Problem Analysis Flowchart:

1. Does the problem require finding/searching a value?
   ├── YES → Use Search Template (1)
   │   ├── Exact match? → Basic binary search
   │   ├── Closest value? → Track min difference
   │   └── Range query? → Prune based on BST property
   └── NO → Continue to 2

2. Does the problem require modifying the BST structure?
   ├── YES → Check modification type
   │   ├── Insert new node? → Use Insertion Template (2)
   │   ├── Delete existing node? → Use Deletion Template (3)
   │   └── Trim/Split tree? → Use modified Deletion Template
   └── NO → Continue to 3

3. Does the problem use the sorted property of BST?
   ├── YES → Use Inorder Template (5)
   │   ├── Kth element? → Inorder with counter
   │   ├── Convert to list? → Inorder traversal
   │   └── Range sum? → Modified inorder
   └── NO → Continue to 4

4. Does the problem require validating BST properties?
   ├── YES → Use Validation Template (4)
   │   ├── Entire tree? → Min/max bounds approach
   │   └── Find largest valid subtree? → Bottom-up validation
   └── NO → Continue to 5

5. Does the problem involve constructing a BST?
   ├── YES → Use Construction Template (6)
   │   ├── From sorted array? → Binary search approach
   │   ├── From traversal? → Use BST properties
   │   └── Generate all possible? → Recursive generation
   └── NO → Continue to 6

6. Does the problem involve paths in the tree?
   ├── YES → Not a BST problem: tree_lca_distance.md (path templates)
   └── NO → Fall back to the plain BST descent (Template 1) or reconsider

// Java BST Node
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

// Iterative inorder with Stack
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
    while (curr != null) {
        stack.push(curr);
        curr = curr.left;
    }
    curr = stack.pop();
    // Process curr
    curr = curr.right;
}

# TreeNode class
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Generator for memory-efficient inorder
def inorder_generator(root):
    if root:
        yield from inorder_generator(root.left)
        yield root.val
        yield from inorder_generator(root.right)