Trees

def inorder_traversal(root: Optional[TreeNode]) -> list[int]:
    """LC 94. Binary Tree Inorder Traversal (iterative).

    Drive a stack: push nodes while walking the left spine, then pop one,
    record it, and switch to its right child. Every stacked node still
    owes its visit; a popped node's left side is already complete. This
    stack version is the one interviews probe -- the recursive form is
    two lines. O(n) time, O(h) space.
    """
    values: list[int] = []
    pending: list[TreeNode] = []
    node = root
    while node or pending:
        while node:  # slide down the left spine, stacking the IOUs
            pending.append(node)
            node = node.left
        node = pending.pop()
        values.append(node.val)
        node = node.right
    return values

// LC 94. Iterative stack: push nodes while walking left, then pop one, record
// it, and switch to its right child. Every stacked node still owes its visit;
// a popped node's left side is already complete.
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    vector<TreeNode*> stack;
    TreeNode* node = root;
    while (node || !stack.empty()) {
        while (node) {
            stack.push_back(node);
            node = node->left;
        }
        node = stack.back();
        stack.pop_back();
        ans.push_back(node->val);
        node = node->right;
    }
    return ans;
}

/// LC 94. Iterative: push while walking left, pop, then switch to the right
/// child. Every stacked node still owes its visit.
pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut ans = Vec::new();
    let mut stack: Vec<Rc<RefCell<TreeNode>>> = Vec::new();
    let mut current = root;
    while current.is_some() || !stack.is_empty() {
        while let Some(node) = current {
            current = node.borrow().left.clone();
            stack.push(node);
        }
        let node = stack.pop().unwrap();
        ans.push(node.borrow().val);
        current = node.borrow().right.clone();
    }
    ans
}

/** LC 94. Iterative: slide left pushing nodes, pop one to visit, then switch to its right child. */
export function inorderTraversal(root: TreeNode | null): number[] {
  const ans: number[] = [];
  const stack: TreeNode[] = [];
  let node = root;
  while (node !== null || stack.length > 0) {
    while (node !== null) {
      stack.push(node); // every stacked node still owes its visit
      node = node.left;
    }
    node = stack.pop()!;
    ans.push(node.val);
    node = node.right;
  }
  return ans;
}

// LC 94. Iterative stack: push nodes while walking the left spine, then pop
// one, record it, and switch to its right child.
func inorderTraversal(root *TreeNode) []int {
	var ans []int
	var stack []*TreeNode
	node := root
	for node != nil || len(stack) > 0 {
		for node != nil {
			stack = append(stack, node)
			node = node.Left
		}
		node = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		ans = append(ans, node.Val)
		node = node.Right
	}
	return ans
}

// LC 94. Iterative stack: push nodes while walking left, then pop one, record
// it, and switch to its right child. Every stacked node still owes its visit.
func inorderTraversal(_ root: TreeNode?) -> [Int] {
    var values: [Int] = []
    var stack: [TreeNode] = []
    var node = root
    while node != nil || !stack.isEmpty {
        while let current = node {  // slide down the left spine, stacking the IOUs
            stack.append(current)
            node = current.left
        }
        let visited = stack.removeLast()
        values.append(visited.val)
        node = visited.right
    }
    return values
}

def preorder_traversal(root: Optional[TreeNode]) -> list[int]:
    """LC 144. Binary Tree Preorder Traversal (iterative).

    Pop a node, record it, then push its right child BEFORE its left so
    the left pops first. The node is handled at pop time, which makes
    preorder the easiest traversal to iterate. O(n) time, O(h) space.
    """
    if not root:
        return []
    values: list[int] = []
    pending: list[TreeNode] = [root]
    while pending:
        node = pending.pop()
        values.append(node.val)
        if node.right:  # right first so left is on top and pops first
            pending.append(node.right)
        if node.left:
            pending.append(node.left)
    return values

// LC 144. Pop a node, record it at pop time, and push its right child before
// its left so the left subtree is processed first.
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;
    if (!root) return ans;
    vector<TreeNode*> stack{root};
    while (!stack.empty()) {
        TreeNode* node = stack.back();
        stack.pop_back();
        ans.push_back(node->val);
        if (node->right) stack.push_back(node->right);
        if (node->left) stack.push_back(node->left);
    }
    return ans;
}

/// LC 144. Pop-and-record; push right BEFORE left so left is handled first.
pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut ans = Vec::new();
    let mut stack = Vec::new();
    if let Some(node) = root {
        stack.push(node);
    }
    while let Some(node) = stack.pop() {
        let node = node.borrow();
        ans.push(node.val);
        if let Some(right) = &node.right {
            stack.push(Rc::clone(right));
        }
        if let Some(left) = &node.left {
            stack.push(Rc::clone(left));
        }
    }
    ans
}

/** LC 144. Iterative: visit at pop time, pushing right BEFORE left so left pops first. */
export function preorderTraversal(root: TreeNode | null): number[] {
  if (!root) return [];
  const ans: number[] = [];
  const stack: TreeNode[] = [root];
  while (stack.length > 0) {
    const node = stack.pop()!;
    ans.push(node.val);
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return ans;
}

// LC 144. Pop a node, record it at pop time, and push its right child before
// its left so the left subtree is processed first.
func preorderTraversal(root *TreeNode) []int {
	var ans []int
	if root == nil {
		return ans
	}
	stack := []*TreeNode{root}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		ans = append(ans, node.Val)
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
	}
	return ans
}

// LC 144. Pop a node, record it at pop time, and push its right child before
// its left so the left subtree is processed first.
func preorderTraversal(_ root: TreeNode?) -> [Int] {
    guard let root = root else { return [] }
    var values: [Int] = []
    var stack: [TreeNode] = [root]
    while let node = stack.popLast() {
        values.append(node.val)
        if let right = node.right { stack.append(right) }  // right first so left pops first
        if let left = node.left { stack.append(left) }
    }
    return values
}

def postorder_traversal(root: Optional[TreeNode]) -> list[int]:
    """LC 145. Binary Tree Postorder Traversal (iterative).

    Run a modified preorder that visits node, right, left (push left
    before right), then reverse the output: reversed(node-right-left)
    is left-right-node, which is postorder. The reversal trick sidesteps
    the awkward state tracking of true one-stack postorder. O(n) time,
    O(n) space.
    """
    if not root:
        return []
    reversed_values: list[int] = []
    pending: list[TreeNode] = [root]
    while pending:
        node = pending.pop()
        reversed_values.append(node.val)
        if node.left:  # left first so right pops first -> node, right, left order
            pending.append(node.left)
        if node.right:
            pending.append(node.right)
    return reversed_values[::-1]

// LC 145. Trick: run a modified preorder that visits node, right, left (push
// left BEFORE right), then reverse the output -- (node, right, left) read
// backwards is exactly (left, right, node). This sidesteps the awkward state
// tracking of true one-stack postorder, where a node must wait for its right
// subtree to finish before it can be emitted.
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ans;
    if (!root) return ans;
    vector<TreeNode*> stack{root};
    while (!stack.empty()) {
        TreeNode* node = stack.back();
        stack.pop_back();
        ans.push_back(node->val);
        if (node->left) stack.push_back(node->left);
        if (node->right) stack.push_back(node->right);
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

/// LC 145. Modified preorder (node, right, left) reversed at the end --
/// sidesteps the state tracking of true one-stack postorder.
pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut ans = Vec::new();
    let mut stack = Vec::new();
    if let Some(node) = root {
        stack.push(node);
    }
    while let Some(node) = stack.pop() {
        let node = node.borrow();
        ans.push(node.val);
        if let Some(left) = &node.left {
            stack.push(Rc::clone(left));
        }
        if let Some(right) = &node.right {
            stack.push(Rc::clone(right));
        }
    }
    ans.reverse();
    ans
}

/** LC 145. Modified preorder visiting node-right-left, then reverse into left-right-node. */
export function postorderTraversal(root: TreeNode | null): number[] {
  if (!root) return [];
  const ans: number[] = [];
  const stack: TreeNode[] = [root];
  while (stack.length > 0) {
    const node = stack.pop()!;
    ans.push(node.val);
    if (node.left) stack.push(node.left); // left under right, so the pop order is node-right-left
    if (node.right) stack.push(node.right);
  }
  return ans.reverse(); // reversed node-right-left IS postorder, no per-node state needed
}

// LC 145. Run a modified preorder that visits node, right, left (push left
// BEFORE right), then reverse the output: (node, right, left) read backwards
// is exactly (left, right, node).
func postorderTraversal(root *TreeNode) []int {
	var ans []int
	if root == nil {
		return ans
	}
	stack := []*TreeNode{root}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		ans = append(ans, node.Val)
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
	}
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return ans
}

// LC 145. Run a modified preorder that visits node, right, left (push left
// BEFORE right), then reverse the output -- read backwards that is exactly
// left, right, node. Sidesteps the state tracking of one-stack postorder.
func postorderTraversal(_ root: TreeNode?) -> [Int] {
    guard let root = root else { return [] }
    var reversedValues: [Int] = []
    var stack: [TreeNode] = [root]
    while let node = stack.popLast() {
        reversedValues.append(node.val)
        if let left = node.left { stack.append(left) }  // left first so right pops first
        if let right = node.right { stack.append(right) }
    }
    return reversedValues.reversed()
}

def invert_tree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    """LC 226. Invert Binary Tree.

    Swap the two child POINTERS at every node, then recurse into both
    sides; one pointer exchange moves whole subtrees, no values change.
    The null root is the only base case. O(n) time, O(h) stack.
    """
    if not root:
        return None
    root.left, root.right = root.right, root.left
    invert_tree(root.left)
    invert_tree(root.right)
    return root

// LC 226. Swap the two child POINTERS at each node -- one exchange moves
// whole subtrees -- then invert each subtree. Null root is the only edge case.
TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

/// LC 226. Swap the child POINTERS (whole subtrees move), then recurse.
pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    if let Some(node) = &root {
        let mut guard = node.borrow_mut();
        let n = &mut *guard; // one deref so the field borrows can split
        std::mem::swap(&mut n.left, &mut n.right);
        invert_tree(n.left.clone());
        invert_tree(n.right.clone());
    }
    root
}

/** LC 226. Swap the two child POINTERS at every node; one swap moves whole subtrees. */
export function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  return root;
}

// LC 226. Swap the two child POINTERS at every node on the way down -- one
// exchange moves whole subtrees -- then recurse into both sides.
func invertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left, root.Right = root.Right, root.Left
	invertTree(root.Left)
	invertTree(root.Right)
	return root
}

// LC 226. Swap children at every node on the way down: one pointer exchange
// moves whole subtrees, then recurse into both sides.
func invertTree(_ root: TreeNode?) -> TreeNode? {
    guard let root = root else { return nil }
    swap(&root.left, &root.right)
    _ = invertTree(root.left)
    _ = invertTree(root.right)
    return root
}

def max_depth(root: Optional[TreeNode]) -> int:
    """LC 104. Maximum Depth of Binary Tree.

    A null node has depth 0; any other node has 1 plus the larger of its
    children's depths. The seed pattern for harder tree problems:
    compute a value bottom up from children. O(n) time, O(h) stack.
    """
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

// LC 104. Bottom-up: a null node has depth 0, any other node has 1 plus the
// larger of its children's depths.
int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

/// LC 104. Null is 0; otherwise 1 + max of the children's depths.
pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    match root {
        None => 0,
        Some(node) => {
            let n = node.borrow();
            1 + max_depth(n.left.clone()).max(max_depth(n.right.clone()))
        }
    }
}

/** LC 104. Bottom up: a node's depth is 1 plus the taller child's depth. */
export function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// LC 104. Bottom up: a null node has depth 0, any other node has 1 plus the
// larger of its children's depths.
func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	left, right := maxDepth(root.Left), maxDepth(root.Right)
	if left > right {
		return 1 + left
	}
	return 1 + right
}

// LC 104. Bottom-up: a null node has depth 0, any other node has 1 plus the
// larger of its children's depths.
func maxDepth(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }
    return 1 + max(maxDepth(root.left), maxDepth(root.right))
}

def diameter_of_binary_tree(root: Optional[TreeNode]) -> int:
    """LC 543. Diameter of Binary Tree -- the postorder return-value pattern.

    Each call returns one fact (height) while a nonlocal best collects a
    different fact (longest path through this node = left height + right
    height). Dozens of tree problems are this exact shape with a
    different combine step. O(n) time, O(height) stack.
    """
    best = 0

    def height(node: Optional[TreeNode]) -> int:
        nonlocal best
        if not node:
            return 0
        left = height(node.left)
        right = height(node.right)
        best = max(best, left + right)
        return 1 + max(left, right)

    height(root)
    return best

// LC 543. Postorder return-value pattern: return height, collect diameter.
static int height(TreeNode* node, int& best) {
    if (!node) return 0;
    int left = height(node->left, best);
    int right = height(node->right, best);
    best = max(best, left + right);
    return 1 + max(left, right);
}

int diameterOfBinaryTree(TreeNode* root) {
    int best = 0;
    height(root, best);
    return best;
}

/// LC 543. Postorder return-value pattern: return height, collect diameter.
pub fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    fn height(node: &Option<Rc<RefCell<TreeNode>>>, best: &mut i32) -> i32 {
        match node {
            None => 0,
            Some(rc) => {
                let n = rc.borrow();
                let left = height(&n.left, best);
                let right = height(&n.right, best);
                *best = (*best).max(left + right);
                1 + left.max(right)
            }
        }
    }
    let mut best = 0;
    height(&root, &mut best);
    best
}

/** LC 543. Postorder return-value pattern: return height, collect diameter. */
export function diameterOfBinaryTree(root: TreeNode | null): number {
  let best = 0;
  function height(node: TreeNode | null): number {
    if (!node) return 0;
    const left = height(node.left);
    const right = height(node.right);
    best = Math.max(best, left + right);
    return 1 + Math.max(left, right);
  }
  height(root);
  return best;
}

// LC 543. Postorder return-value pattern: return height, collect diameter.
func diameterOfBinaryTree(root *TreeNode) int {
	best := 0
	var height func(node *TreeNode) int
	height = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		left := height(node.Left)
		right := height(node.Right)
		if left+right > best {
			best = left + right
		}
		if left > right {
			return 1 + left
		}
		return 1 + right
	}
	height(root)
	return best
}

// LC 543. Postorder return-value pattern: return height, collect diameter.
func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
    var best = 0
    func height(_ node: TreeNode?) -> Int {
        guard let node = node else { return 0 }
        let left = height(node.left)
        let right = height(node.right)
        best = max(best, left + right)
        return 1 + max(left, right)
    }
    _ = height(root)
    return best
}

def is_balanced(root: Optional[TreeNode]) -> bool:
    """LC 110. Balanced Binary Tree (single pass).

    Compute heights bottom up, but return -1 as a sentinel the moment
    any subtree is unbalanced and propagate it straight up with no
    further work. Folding the boolean into the height return keeps it
    O(n); the naive version recomputes heights per node and degrades to
    O(n^2). O(h) stack.
    """

    def subtree_height(node: Optional[TreeNode]) -> int:
        if not node:
            return 0
        left = subtree_height(node.left)
        if left == -1:  # short-circuit: a deeper imbalance already decided the answer
            return -1
        right = subtree_height(node.right)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return subtree_height(root) != -1

// LC 110. Single pass: DFS returns height, or -1 the moment any subtree is
// unbalanced, and the sentinel propagates straight up with no further work.
// Folding the boolean into the height return keeps it O(n).
bool isBalanced(TreeNode* root) {
    auto height = [&](auto&& self, TreeNode* node) -> int {
        if (!node) return 0;
        int left = self(self, node->left);
        if (left == -1) return -1;
        int right = self(self, node->right);
        if (right == -1 || abs(left - right) > 1) return -1;
        return 1 + max(left, right);
    };
    return height(height, root) != -1;
}

/// LC 110. Bottom-up heights with -1 as the "already unbalanced" sentinel,
/// folding the boolean into the height return keeps it O(n).
pub fn is_balanced(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    fn height(node: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        match node {
            None => 0,
            Some(rc) => {
                let n = rc.borrow();
                let left = height(&n.left);
                if left == -1 {
                    return -1;
                }
                let right = height(&n.right);
                if right == -1 || (left - right).abs() > 1 {
                    return -1;
                }
                1 + left.max(right)
            }
        }
    }
    height(&root) != -1
}

/** LC 110. Single pass: height() returns -1 the moment any subtree tilts, and the sentinel rides up. */
export function isBalanced(root: TreeNode | null): boolean {
  function height(node: TreeNode | null): number {
    if (!node) return 0;
    const left = height(node.left);
    if (left === -1) return -1;
    const right = height(node.right);
    if (right === -1) return -1;
    if (Math.abs(left - right) > 1) return -1;
    return 1 + Math.max(left, right);
  }
  return height(root) !== -1;
}

// LC 110. Single pass: DFS returns height, or -1 the moment any subtree is
// unbalanced, and the sentinel propagates straight up with no further work.
func isBalanced(root *TreeNode) bool {
	var height func(node *TreeNode) int
	height = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		left := height(node.Left)
		if left == -1 {
			return -1
		}
		right := height(node.Right)
		if right == -1 || left-right > 1 || right-left > 1 {
			return -1
		}
		if left > right {
			return 1 + left
		}
		return 1 + right
	}
	return height(root) != -1
}

// LC 110. Single pass: DFS returns height, or -1 the moment any subtree is
// unbalanced, and the sentinel propagates straight up with no further work.
func isBalanced(_ root: TreeNode?) -> Bool {
    func height(_ node: TreeNode?) -> Int {
        guard let node = node else { return 0 }
        let left = height(node.left)
        if left == -1 { return -1 }  // a deeper imbalance already decided the answer
        let right = height(node.right)
        if right == -1 || abs(left - right) > 1 { return -1 }
        return 1 + max(left, right)
    }
    return height(root) != -1
}

def is_same_tree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    """LC 100. Same Tree.

    Recurse on both trees in lockstep: two nulls match, one null or a
    value mismatch fails, otherwise combine the left-pair and right-pair
    checks. Null cases come before touching .val -- that ordering is the
    safety. O(n) time, O(h) stack.
    """
    if not p and not q:
        return True
    if not p or not q or p.val != q.val:
        return False
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

// LC 100. Recurse on both trees simultaneously: two nulls match, one null or
// a value mismatch fails, otherwise both child pairs must match. Null checks
// come before touching values.
bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q || p->val != q->val) return false;
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

/// LC 100. Simultaneous recursion: two nulls match, one null or a value
/// mismatch fails, otherwise AND the left pair and the right pair.
pub fn is_same_tree(p: Option<Rc<RefCell<TreeNode>>>, q: Option<Rc<RefCell<TreeNode>>>) -> bool {
    match (p, q) {
        (None, None) => true,
        (Some(a), Some(b)) => {
            let a = a.borrow();
            let b = b.borrow();
            a.val == b.val
                && is_same_tree(a.left.clone(), b.left.clone())
                && is_same_tree(a.right.clone(), b.right.clone())
        }
        _ => false,
    }
}

/** LC 100. March both trees in lockstep: two nulls match; one null or differing values do not. */
export function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  if (!p && !q) return true;
  if (!p || !q || p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

// LC 100. Recurse on both trees in lockstep: two nulls match, one null or a
// value mismatch fails; null checks come before touching values.
func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}
	if p == nil || q == nil || p.Val != q.Val {
		return false
	}
	return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

// LC 100. Recurse on both trees in lockstep: two nils match, one nil or a
// value mismatch fails, otherwise both child pairs must match.
func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
    if p == nil && q == nil { return true }
    guard let p = p, let q = q, p.val == q.val else { return false }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}

def is_subtree(root: Optional[TreeNode], sub_root: Optional[TreeNode]) -> bool:
    """LC 572. Subtree of Another Tree.

    Traverse root and run a full Same Tree comparison against sub_root
    at every node, returning True on the first hit. A subtree means a
    node plus ALL its descendants, so a matching region that continues
    below sub_root's leaves does not count -- the same-tree check
    enforces that for free. O(m * n) time, O(h) stack.
    """
    if not root:
        return sub_root is None
    if is_same_tree(root, sub_root):
        return True
    return is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)

// LC 572. At every node of root, run the full Same Tree check against
// subRoot. A subtree is a node plus ALL its descendants, so a match that
// continues below subRoot's leaves does not count. O(m * n).
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    if (!root) return subRoot == nullptr;
    if (isSameTree(root, subRoot)) return true;
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

/// LC 572. Run a full Same Tree check at every node of root; O(m * n).
pub fn is_subtree(
    root: Option<Rc<RefCell<TreeNode>>>,
    sub_root: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
    if is_same_tree(root.clone(), sub_root.clone()) {
        return true;
    }
    match root {
        None => false,
        Some(node) => {
            let n = node.borrow();
            is_subtree(n.left.clone(), sub_root.clone()) || is_subtree(n.right.clone(), sub_root)
        }
    }
}

/** LC 572. At every node of root, run a full isSameTree against subRoot. */
export function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
  if (!root) return false; // subRoot has at least one node per constraints
  if (isSameTree(root, subRoot)) return true;
  return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

// LC 572. Run a full same-tree check at every node of root; a matching region
// that continues below subRoot's leaves does not count. O(m * n).
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
	var same func(p, q *TreeNode) bool
	same = func(p, q *TreeNode) bool {
		if p == nil && q == nil {
			return true
		}
		if p == nil || q == nil || p.Val != q.Val {
			return false
		}
		return same(p.Left, q.Left) && same(p.Right, q.Right)
	}
	var dfs func(node *TreeNode) bool
	dfs = func(node *TreeNode) bool {
		if node == nil {
			return subRoot == nil
		}
		if same(node, subRoot) {
			return true
		}
		return dfs(node.Left) || dfs(node.Right)
	}
	return dfs(root)
}

// LC 572. At every node of root, run the full Same Tree check against
// subRoot; a match that continues below subRoot's leaves does not count.
func isSubtree(_ root: TreeNode?, _ subRoot: TreeNode?) -> Bool {
    func same(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        if p == nil && q == nil { return true }
        guard let p = p, let q = q, p.val == q.val else { return false }
        return same(p.left, q.left) && same(p.right, q.right)
    }
    guard let root = root else { return subRoot == nil }
    if same(root, subRoot) { return true }
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)
}

def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    """LC 235. Lowest Common Ancestor of a Binary Search Tree.

    Walk down from the root using BST ordering: both values smaller go
    left, both larger go right, and the first node where they split (or
    one equals it) is the LCA. A node counts as its own ancestor. No
    recursion needed. O(h) time, O(1) space.
    """
    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  # p and q split here (or one IS this node)
    return root

// LC 235. BST walk: while both values sit on the same side, descend; the
// first node where they split (or that equals p or q) is the LCA, since a
// node counts as its own ancestor. O(h), no recursion needed.
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode* node = root;
    while (node) {
        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 break;  // split point, or node equals p or q
    }
    return node;
}

/// LC 235. BST walk by values: both smaller go left, both larger go right,
/// stop at the split point (a node counts as its own ancestor). O(h).
pub fn lowest_common_ancestor(
    root: Option<Rc<RefCell<TreeNode>>>,
    p: Option<Rc<RefCell<TreeNode>>>,
    q: Option<Rc<RefCell<TreeNode>>>,
) -> Option<Rc<RefCell<TreeNode>>> {
    let p_val = p?.borrow().val;
    let q_val = q?.borrow().val;
    let mut node = root;
    while let Some(rc) = node {
        let val = rc.borrow().val;
        if p_val < val && q_val < val {
            node = rc.borrow().left.clone();
        } else if p_val > val && q_val > val {
            node = rc.borrow().right.clone();
        } else {
            return Some(rc);
        }
    }
    None
}

/** LC 235. BST walk: descend while both values sit on the same side; the split point is the LCA. */
export function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  let node = root;
  while (node) {
    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; // the values split here, or one equals node (a node is its own ancestor)
  }
  return null;
}

// LC 235. BST walk: while both values sit on the same side, descend; the
// first node where they split (or that equals p or q) is the LCA.
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	node := root
	for node != nil {
		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 {
			break // split point, or node equals p or q
		}
	}
	return node
}

// LC 235. BST walk: while both values sit on the same side, descend; the
// first node where they split (or that equals p or q) is the LCA.
func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
    guard let p = p, let q = q else { return nil }
    var node = root
    while let current = node {
        if p.val < current.val && q.val < current.val {
            node = current.left
        } else if p.val > current.val && q.val > current.val {
            node = current.right
        } else {
            return current  // split point, or current equals p or q
        }
    }
    return nil
}

def insert_into_bst(root: Optional[TreeNode], val: int) -> TreeNode:
    """LC 701. Insert into a Binary Search Tree.

    Walk down -- left when val is smaller, right when larger -- until a
    null child slot appears, then attach a new leaf there. No
    rebalancing needed since any valid BST is accepted; the empty tree
    is the only edge case. O(h) time, O(1) space.
    """
    leaf = TreeNode(val)
    if not root:
        return leaf
    node = root
    while True:
        if val < node.val:
            if not node.left:
                node.left = leaf
                return root
            node = node.left
        else:
            if not node.right:
                node.right = leaf
                return root
            node = node.right

// LC 701. Walk down to the null slot the value belongs in and attach a leaf;
// no rebalancing is required since any valid BST is accepted. The recursion
// reattaches each child pointer on the way back up.
TreeNode* insertIntoBST(TreeNode* root, int 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;
}

/// LC 701. Walk down by comparison until a null slot appears, attach a leaf.
/// Empty tree: the new node itself is the answer.
pub fn insert_into_bst(
    root: Option<Rc<RefCell<TreeNode>>>,
    val: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
    match root {
        None => Some(Rc::new(RefCell::new(TreeNode::new(val)))),
        Some(node) => {
            {
                let mut n = node.borrow_mut();
                if val < n.val {
                    n.left = insert_into_bst(n.left.take(), val);
                } else {
                    n.right = insert_into_bst(n.right.take(), val);
                }
            }
            Some(node)
        }
    }
}

/** LC 701. Walk down by comparison until a null slot appears, then hang the new leaf there. */
export function insertIntoBST(root: TreeNode | null, val: number): TreeNode {
  if (!root) return new TreeNode(val);
  let node = root;
  while (true) {
    if (val < node.val) {
      if (!node.left) {
        node.left = new TreeNode(val);
        return root;
      }
      node = node.left;
    } else {
      if (!node.right) {
        node.right = new TreeNode(val);
        return root;
      }
      node = node.right;
    }
  }
}

// LC 701. Walk down to the null slot the value belongs in and attach a leaf;
// the recursion reattaches each child pointer on the way back up.
func insertIntoBST(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return &TreeNode{Val: val}
	}
	if val < root.Val {
		root.Left = insertIntoBST(root.Left, val)
	} else {
		root.Right = insertIntoBST(root.Right, val)
	}
	return root
}

// LC 701. Walk down to the null slot the value belongs in and attach a leaf;
// the recursion reattaches each child pointer on the way back up.
func insertIntoBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
    guard let root = root else { return TreeNode(val) }
    if val < root.val {
        root.left = insertIntoBST(root.left, val)
    } else {
        root.right = insertIntoBST(root.right, val)
    }
    return root
}

def delete_node(root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
    """LC 450. Delete Node in a BST.

    Recurse to the node, then three cases: no left child -> return the
    right child; no right child -> return the left child; two children
    -> copy in the inorder successor's value and delete that successor
    from the right subtree. The successor (leftmost of the right
    subtree) never has a left child, so the second deletion hits an
    easy case. O(h) time, O(h) stack.
    """
    if not root:
        return None
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        if not root.left:
            return root.right  # covers the leaf case too (right is None)
        if not root.right:
            return root.left
        successor = root.right
        while successor.left:
            successor = successor.left
        root.val = successor.val
        root.right = delete_node(root.right, successor.val)
    return root

// LC 450. Recurse to the key. With at most one child, return the other one.
// With two children, copy in the inorder successor's value -- the leftmost
// node of the right subtree, which never has a left child -- then delete that
// successor from the right subtree, where it hits an easy case.
TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
    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) return root->right;
        if (!root->right) return root->left;
        TreeNode* successor = root->right;
        while (successor->left) successor = successor->left;
        root->val = successor->val;
        root->right = deleteNode(root->right, successor->val);
    }
    return root;
}

/// LC 450. At most one child: return the other side. Two children: copy in
/// the inorder successor (leftmost of the right subtree, which never has a
/// left child), then delete that successor from the right subtree.
pub fn delete_node(root: Option<Rc<RefCell<TreeNode>>>, key: i32) -> Option<Rc<RefCell<TreeNode>>> {
    let node = root?;
    let node_val = node.borrow().val;
    if key < node_val {
        let left = node.borrow_mut().left.take();
        node.borrow_mut().left = delete_node(left, key);
        return Some(node);
    }
    if key > node_val {
        let right = node.borrow_mut().right.take();
        node.borrow_mut().right = delete_node(right, key);
        return Some(node);
    }
    let left = node.borrow_mut().left.take();
    let right = node.borrow_mut().right.take();
    match (left, right) {
        (None, child) => child,
        (child, None) => child,
        (l, r) => {
            let mut successor = Rc::clone(r.as_ref().unwrap());
            loop {
                let next = successor.borrow().left.clone();
                match next {
                    Some(n) => successor = n,
                    None => break,
                }
            }
            let succ_val = successor.borrow().val;
            let new_right = delete_node(r, succ_val);
            let mut n = node.borrow_mut();
            n.val = succ_val;
            n.left = l;
            n.right = new_right;
            drop(n);
            Some(node)
        }
    }
}

/** LC 450. With two children, copy in the inorder successor's value, then delete IT from the right subtree. */
export function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  if (!root) 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) return root.right; // zero or one child: splice it straight in
    if (!root.right) return root.left;
    let successor = root.right;
    while (successor.left) successor = successor.left; // leftmost of right never has a left child
    root.val = successor.val;
    root.right = deleteNode(root.right, successor.val); // the second deletion hits an easy case
  }
  return root;
}

// LC 450. Three cases: missing a child, return the other one; two children,
// copy in the inorder successor's value (leftmost of the right subtree, which
// never has a left child) and delete that successor from the right subtree.
func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return nil
	}
	switch {
	case key < root.Val:
		root.Left = deleteNode(root.Left, key)
	case key > root.Val:
		root.Right = deleteNode(root.Right, key)
	default:
		if root.Left == nil {
			return root.Right
		}
		if root.Right == nil {
			return root.Left
		}
		successor := root.Right
		for successor.Left != nil {
			successor = successor.Left
		}
		root.Val = successor.Val
		root.Right = deleteNode(root.Right, successor.Val)
	}
	return root
}

// LC 450. Recurse to the key, then three cases: at most one child returns the
// other; two children copy in the inorder successor's value (leftmost of the
// right subtree, never has a left child) and delete it from the right side.
func deleteNode(_ root: TreeNode?, _ key: Int) -> TreeNode? {
    guard let root = root else { return nil }
    if key < root.val {
        root.left = deleteNode(root.left, key)
    } else if key > root.val {
        root.right = deleteNode(root.right, key)
    } else {
        guard let left = root.left else { return root.right }  // covers the leaf case too
        guard let right = root.right else { return left }
        var successor = right
        while let next = successor.left { successor = next }
        root.val = successor.val
        root.right = deleteNode(root.right, successor.val)
    }
    return root
}

def level_order(root: Optional[TreeNode]) -> list[list[int]]:
    """LC 102. Binary Tree Level Order Traversal.

    Knob: snapshot len(queue) before each round so one while-iteration
    consumes exactly one level. O(n) time, O(width) space.
    """
    if not root:
        return []
    ans: list[list[int]] = []
    queue = deque([root])
    while queue:
        level: list[int] = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        ans.append(level)
    return ans

// LC 102. Snapshot the queue size so each while-round consumes one level.
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    if (!root) return ans;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int levelSize = static_cast<int>(q.size());
        vector<int> level;
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        ans.push_back(level);
    }
    return ans;
}

/// LC 102. Snapshot the queue length so each while-round consumes one level.
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
    let mut ans = Vec::new();
    let mut queue = VecDeque::new();
    if let Some(node) = root {
        queue.push_back(node);
    }
    while !queue.is_empty() {
        let level_size = queue.len();
        let mut level = Vec::with_capacity(level_size);
        for _ in 0..level_size {
            let node = queue.pop_front().unwrap();
            let node = node.borrow();
            level.push(node.val);
            if let Some(left) = &node.left {
                queue.push_back(Rc::clone(left));
            }
            if let Some(right) = &node.right {
                queue.push_back(Rc::clone(right));
            }
        }
        ans.push(level);
    }
    ans
}

/** LC 102. Snapshot the queue length so each while-round consumes one level. */
export function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const ans: number[][] = [];
  let queue: TreeNode[] = [root];
  while (queue.length > 0) {
    const next: TreeNode[] = [];
    const level: number[] = [];
    for (const node of queue) {
      level.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    ans.push(level);
    queue = next; // swap whole levels instead of shifting one by one
  }
  return ans;
}

// LC 102. Snapshot the queue length so each while-round consumes one level.
func levelOrder(root *TreeNode) [][]int {
	ans := [][]int{}
	if root == nil {
		return ans
	}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		levelSize := len(queue)
		level := make([]int, 0, levelSize)
		for i := 0; i < levelSize; i++ {
			node := queue[0]
			queue = queue[1:]
			level = append(level, node.Val)
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		ans = append(ans, level)
	}
	return ans
}

// LC 102. Snapshot the queue count so each while-round consumes one level.
func levelOrder(_ root: TreeNode?) -> [[Int]] {
    guard let root = root else { return [] }
    var ans: [[Int]] = []
    var queue: [TreeNode] = [root]
    var head = 0
    while head < queue.count {
        let levelEnd = queue.count
        var level: [Int] = []
        while head < levelEnd {
            let node = queue[head]
            head += 1
            level.append(node.val)
            if let left = node.left { queue.append(left) }
            if let right = node.right { queue.append(right) }
        }
        ans.append(level)
    }
    return ans
}

def right_side_view(root: Optional[TreeNode]) -> list[int]:
    """LC 199. Binary Tree Right Side View.

    BFS with the size-snapshot pattern, keeping the LAST node of each
    level. Per-level tracking is essential: the rightmost node is not
    always a right child -- a deep left branch can stick out past a
    shallow right side. O(n) time, O(w) space.
    """
    if not root:
        return []
    view: list[int] = []
    frontier: deque[TreeNode] = deque([root])
    while frontier:
        for _ in range(len(frontier)):  # snapshot keeps level boundaries intact
            node = frontier.popleft()
            for child in (node.left, node.right):
                if child:
                    frontier.append(child)
        view.append(node.val)  # node is the last one popped on this level
    return view

// LC 199. BFS with the size-snapshot pattern, keeping the last node of each
// level. The rightmost node is not always a right child -- a deep left branch
// can stick out past a shallow right side -- so per-level tracking is key.
vector<int> rightSideView(TreeNode* root) {
    vector<int> ans;
    if (!root) return ans;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int levelSize = static_cast<int>(q.size());
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();
            if (i == levelSize - 1) ans.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return ans;
}

/// LC 199. DFS right child first, recording the first node seen at each new
/// depth; per-level tracking matters because a deep left branch can stick
/// out past a shallow right side.
pub fn right_side_view(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, depth: usize, view: &mut Vec<i32>) {
        if let Some(rc) = node {
            let n = rc.borrow();
            if depth == view.len() {
                view.push(n.val);
            }
            dfs(&n.right, depth + 1, view);
            dfs(&n.left, depth + 1, view);
        }
    }
    let mut view = Vec::new();
    dfs(&root, 0, &mut view);
    view
}

/** LC 199. Level-order with the size-snapshot pattern; keep only the last node of each level. */
export function rightSideView(root: TreeNode | null): number[] {
  if (!root) return [];
  const ans: number[] = [];
  let queue: TreeNode[] = [root];
  while (queue.length > 0) {
    ans.push(queue[queue.length - 1].val); // a deep LEFT branch can stick out past the right side
    const next: TreeNode[] = [];
    for (const node of queue) {
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    queue = next;
  }
  return ans;
}

// LC 199. BFS with the size-snapshot pattern, keeping the last node of each
// level; a deep left branch can stick out past a shallow right side.
func rightSideView(root *TreeNode) []int {
	var ans []int
	if root == nil {
		return ans
	}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		levelSize := len(queue)
		for i := 0; i < levelSize; i++ {
			node := queue[0]
			queue = queue[1:]
			if i == levelSize-1 {
				ans = append(ans, node.Val)
			}
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
	}
	return ans
}

// LC 199. BFS with the size-snapshot pattern, keeping the LAST node of each
// level -- a deep left branch can stick out past a shallow right side.
func rightSideView(_ root: TreeNode?) -> [Int] {
    guard let root = root else { return [] }
    var view: [Int] = []
    var frontier: [TreeNode] = [root]
    var head = 0
    while head < frontier.count {
        let levelEnd = frontier.count  // snapshot keeps level boundaries intact
        while head < levelEnd {
            let node = frontier[head]
            head += 1
            if head == levelEnd { view.append(node.val) }
            if let left = node.left { frontier.append(left) }
            if let right = node.right { frontier.append(right) }
        }
    }
    return view
}

def construct_quad_tree(grid: list[list[int]]) -> QuadNode:
    """LC 427. Construct Quad Tree.

    Recurse on the four quadrants of an n x n binary grid (n a power of
    two). The merge test AFTER recursion is the heart of it: if all four
    children come back as leaves sharing one value, collapse them into a
    single leaf; otherwise wrap them in an internal node. Base case is a
    single cell. O(n^2) time, O(log n) stack.
    """

    def build(row: int, col: int, size: int) -> QuadNode:
        if size == 1:
            return QuadNode(val=bool(grid[row][col]), isLeaf=True)
        half = size // 2
        top_left = build(row, col, half)
        top_right = build(row, col + half, half)
        bottom_left = build(row + half, col, half)
        bottom_right = build(row + half, col + half, half)
        quadrants = (top_left, top_right, bottom_left, bottom_right)
        # merge only when all four are leaves agreeing on one value
        if all(q.isLeaf for q in quadrants) and len({q.val for q in quadrants}) == 1:
            return QuadNode(val=top_left.val, isLeaf=True)
        return QuadNode(True, False, top_left, top_right, bottom_left, bottom_right)

    return build(0, 0, len(grid))

// LC 427. Recurse on the four quadrants; if all four children come back as
// leaves sharing one value, collapse them into a single leaf, otherwise wrap
// them in an internal node. The merge test AFTER recursion is the heart of
// it; the base case is a single cell.
QuadNode* constructQuadTree(vector<vector<int>> grid) {
    auto build = [&](auto&& self, int row, int col, int size) -> QuadNode* {
        if (size == 1) return new QuadNode(grid[row][col], true);
        int half = size / 2;
        QuadNode* tl = self(self, row, col, half);
        QuadNode* tr = self(self, row, col + half, half);
        QuadNode* bl = self(self, row + half, col, half);
        QuadNode* br = self(self, row + half, col + half, half);
        if (tl->isLeaf && tr->isLeaf && bl->isLeaf && br->isLeaf &&
            tl->val == tr->val && tr->val == bl->val && bl->val == br->val) {
            int value = tl->val;
            delete tl;
            delete tr;
            delete bl;
            delete br;
            return new QuadNode(value, true);
        }
        return new QuadNode(1, false, tl, tr, bl, br);  // internal val is arbitrary
    };
    return build(build, 0, 0, static_cast<int>(grid.size()));
}

/// LC 427. Recurse on the four quadrants; if all four come back as leaves
/// sharing one value, collapse them into a single leaf. The merge test runs
/// AFTER the recursion; the base case is a single cell.
pub fn construct_quad_tree(grid: Vec<Vec<i32>>) -> Option<Rc<RefCell<QuadNode>>> {
    fn build(grid: &[Vec<i32>], row: usize, col: usize, size: usize) -> Rc<RefCell<QuadNode>> {
        if size == 1 {
            return Rc::new(RefCell::new(QuadNode {
                val: grid[row][col] == 1,
                is_leaf: true,
                top_left: None,
                top_right: None,
                bottom_left: None,
                bottom_right: None,
            }));
        }
        let half = size / 2;
        let tl = build(grid, row, col, half);
        let tr = build(grid, row, col + half, half);
        let bl = build(grid, row + half, col, half);
        let br = build(grid, row + half, col + half, half);
        let children = [&tl, &tr, &bl, &br];
        if children.iter().all(|c| c.borrow().is_leaf) {
            let val = tl.borrow().val;
            if children.iter().all(|c| c.borrow().val == val) {
                return tl; // uniform quadrant collapses to one leaf
            }
        }
        Rc::new(RefCell::new(QuadNode {
            val: true,
            is_leaf: false,
            top_left: Some(tl),
            top_right: Some(tr),
            bottom_left: Some(bl),
            bottom_right: Some(br),
        }))
    }
    if grid.is_empty() {
        return None;
    }
    let n = grid.len();
    Some(build(&grid, 0, 0, n))
}

/** LC 427. Recurse on the four quadrants; collapse them when all four return as leaves sharing one value. */
export function constructQuadTree(grid: number[][]): QuadNode {
  function build(row: number, col: number, size: number): QuadNode {
    if (size === 1) return new QuadNode(grid[row][col] === 1, true);
    const half = size / 2;
    const topLeft = build(row, col, half);
    const topRight = build(row, col + half, half);
    const bottomLeft = build(row + half, col, half);
    const bottomRight = build(row + half, col + half, half);
    if (
      topLeft.isLeaf &&
      topRight.isLeaf &&
      bottomLeft.isLeaf &&
      bottomRight.isLeaf &&
      topLeft.val === topRight.val &&
      topLeft.val === bottomLeft.val &&
      topLeft.val === bottomRight.val
    ) {
      return new QuadNode(topLeft.val, true); // the merge test AFTER recursion is the heart of it
    }
    return new QuadNode(true, false, topLeft, topRight, bottomLeft, bottomRight);
  }
  return build(0, 0, grid.length);
}

// LC 427. Recurse on the four quadrants; if all four children come back as
// leaves sharing one value, collapse them into a single leaf, otherwise wrap
// them in an internal node. The merge test AFTER recursion is the heart of it.
func constructQuadTree(grid [][]int) *Node {
	var build func(row, col, size int) *Node
	build = func(row, col, size int) *Node {
		if size == 1 {
			return &Node{Val: grid[row][col] == 1, IsLeaf: true}
		}
		half := size / 2
		tl := build(row, col, half)
		tr := build(row, col+half, half)
		bl := build(row+half, col, half)
		br := build(row+half, col+half, half)
		if tl.IsLeaf && tr.IsLeaf && bl.IsLeaf && br.IsLeaf &&
			tl.Val == tr.Val && tr.Val == bl.Val && bl.Val == br.Val {
			return &Node{Val: tl.Val, IsLeaf: true}
		}
		return &Node{Val: true, IsLeaf: false, TopLeft: tl, TopRight: tr, BottomLeft: bl, BottomRight: br}
	}
	return build(0, 0, len(grid))
}

// LC 427. Recurse on the four quadrants; if all four children come back as
// leaves sharing one value, collapse them into a single leaf, otherwise wrap
// them in an internal node. The merge test AFTER recursion is the heart of it.
func constructQuadTree(_ grid: [[Int]]) -> Node? {
    func build(_ row: Int, _ col: Int, _ size: Int) -> Node {
        if size == 1 { return Node(grid[row][col] == 1, true) }
        let half = size / 2
        let topLeft = build(row, col, half)
        let topRight = build(row, col + half, half)
        let bottomLeft = build(row + half, col, half)
        let bottomRight = build(row + half, col + half, half)
        if topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf
            && topLeft.val == topRight.val && topRight.val == bottomLeft.val
            && bottomLeft.val == bottomRight.val {
            return Node(topLeft.val, true)
        }
        return Node(true, false, topLeft, topRight, bottomLeft, bottomRight)  // internal val is arbitrary
    }
    return build(0, 0, grid.count)
}

def good_nodes(root: TreeNode) -> int:
    """LC 1448. Count Good Nodes in Binary Tree.

    DFS carrying the path maximum DOWN as a parameter: a node is good
    when its value is at least the max seen on the root-to-node path,
    and the max updates before recursing into the children. Information
    flows top down here, not bottom up; the root is always good. O(n)
    time, O(h) stack.
    """

    def count_good(node: Optional[TreeNode], path_max: int) -> int:
        if not node:
            return 0
        good = 1 if node.val >= path_max else 0
        path_max = max(path_max, node.val)
        return good + count_good(node.left, path_max) + count_good(node.right, path_max)

    return count_good(root, root.val)

// LC 1448. DFS carries the path maximum DOWN as a parameter (top-down flow,
// not a bottom-up return); a node is good when its value is at least that
// maximum, and the maximum updates before recursing. The root always counts.
int goodNodes(TreeNode* root) {
    auto dfs = [&](auto&& self, TreeNode* node, int pathMax) -> int {
        if (!node) return 0;
        int count = node->val >= pathMax ? 1 : 0;
        int newMax = max(pathMax, node->val);
        return count + self(self, node->left, newMax) + self(self, node->right, newMax);
    };
    return dfs(dfs, root, INT_MIN);
}

/// LC 1448. Carry the path maximum DOWN as a parameter (top-down info flow);
/// a node is good when its value is at least that maximum.
pub fn good_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, path_max: i32) -> i32 {
        match node {
            None => 0,
            Some(rc) => {
                let n = rc.borrow();
                let good = (n.val >= path_max) as i32;
                let path_max = path_max.max(n.val);
                good + dfs(&n.left, path_max) + dfs(&n.right, path_max)
            }
        }
    }
    dfs(&root, i32::MIN)
}

/** LC 1448. Carry the path maximum DOWN as a parameter; a node at least that max is good. */
export function goodNodes(root: TreeNode | null): number {
  function count(node: TreeNode | null, pathMax: number): number {
    if (!node) return 0;
    const good = node.val >= pathMax ? 1 : 0;
    const nextMax = Math.max(pathMax, node.val); // update before recursing into the children
    return good + count(node.left, nextMax) + count(node.right, nextMax);
  }
  return count(root, -Infinity); // the root always counts as good
}

// LC 1448. DFS carries the path maximum DOWN as a parameter; a node is good
// when its value is at least that maximum. The root always counts.
func goodNodes(root *TreeNode) int {
	var dfs func(node *TreeNode, pathMax int) int
	dfs = func(node *TreeNode, pathMax int) int {
		if node == nil {
			return 0
		}
		count := 0
		if node.Val >= pathMax {
			count = 1
		}
		if node.Val > pathMax {
			pathMax = node.Val
		}
		return count + dfs(node.Left, pathMax) + dfs(node.Right, pathMax)
	}
	return dfs(root, math.MinInt32)
}

// LC 1448. DFS carries the path maximum DOWN as a parameter (top-down flow,
// not a bottom-up return); the maximum updates before recursing.
func goodNodes(_ root: TreeNode?) -> Int {
    func countGood(_ node: TreeNode?, _ pathMax: Int) -> Int {
        guard let node = node else { return 0 }
        let good = node.val >= pathMax ? 1 : 0
        let newMax = max(pathMax, node.val)
        return good + countGood(node.left, newMax) + countGood(node.right, newMax)
    }
    return countGood(root, Int.min)
}

def is_valid_bst(root: Optional[TreeNode]) -> bool:
    """LC 98. Validate Binary Search Tree.

    DFS passing down an open interval (lo, hi) every node must fall
    inside: the left child narrows hi to the node's value, the right
    child raises lo. Checking only parent against children misses
    grandparent violations -- the bounds must travel with the recursion.
    O(n) time, O(h) stack.
    """

    def within(node: Optional[TreeNode], lo: float, hi: float) -> bool:
        if not node:
            return True
        if not (lo < node.val < hi):  # strict: equal values are invalid
            return False
        return within(node.left, lo, node.val) and within(node.right, node.val, hi)

    return within(root, float("-inf"), float("inf"))

// LC 98. Pass down an open interval (lo, hi): each node must fall strictly
// inside it, the left child narrows hi to the node's value, the right child
// raises lo. Checking only parent vs children misses grandparent violations.
// long long bounds let INT_MIN/INT_MAX node values sit strictly inside the
// initial interval.
bool isValidBST(TreeNode* root) {
    auto dfs = [&](auto&& self, TreeNode* node, long long lo, long long hi) -> bool {
        if (!node) return true;
        if (node->val <= lo || node->val >= hi) return false;
        return self(self, node->left, lo, node->val) && self(self, node->right, node->val, hi);
    };
    return dfs(dfs, root, LLONG_MIN, LLONG_MAX);
}

/// LC 98. Pass an open (lo, hi) interval down in i64 so i32::MIN/MAX node
/// values still have room; parent-vs-child checks miss grandparent violations.
pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    fn check(node: &Option<Rc<RefCell<TreeNode>>>, lo: i64, hi: i64) -> bool {
        match node {
            None => true,
            Some(rc) => {
                let n = rc.borrow();
                let val = n.val as i64;
                lo < val && val < hi && check(&n.left, lo, val) && check(&n.right, val, hi)
            }
        }
    }
    check(&root, i64::MIN, i64::MAX)
}

/** LC 98. Pass an open (lo, hi) interval down; parent-vs-child checks miss grandparent violations. */
export function isValidBST(root: TreeNode | null): boolean {
  function inBounds(node: TreeNode | null, lo: number, hi: number): boolean {
    if (!node) return true;
    if (node.val <= lo || node.val >= hi) return false;
    return inBounds(node.left, lo, node.val) && inBounds(node.right, node.val, hi);
  }
  return inBounds(root, -Infinity, Infinity);
}

// LC 98. Pass down an open interval (lo, hi) every node must fall strictly
// inside: the left child narrows hi, the right child raises lo. int64 bounds
// let extreme int32 node values sit strictly inside the initial interval.
func isValidBST(root *TreeNode) bool {
	var dfs func(node *TreeNode, lo, hi int64) bool
	dfs = func(node *TreeNode, lo, hi int64) bool {
		if node == nil {
			return true
		}
		v := int64(node.Val)
		if v <= lo || v >= hi {
			return false
		}
		return dfs(node.Left, lo, v) && dfs(node.Right, v, hi)
	}
	return dfs(root, math.MinInt64, math.MaxInt64)
}

// LC 98. Pass down an open interval (lo, hi) every node must fall strictly
// inside; checking only parent vs children misses grandparent violations.
func isValidBST(_ root: TreeNode?) -> Bool {
    func within(_ node: TreeNode?, _ lo: Int, _ hi: Int) -> Bool {
        guard let node = node else { return true }
        if node.val <= lo || node.val >= hi { return false }  // strict: equal values are invalid
        return within(node.left, lo, node.val) && within(node.right, node.val, hi)
    }
    return within(root, Int.min, Int.max)
}

def kth_smallest(root: Optional[TreeNode], k: int) -> int:
    """LC 230. Kth Smallest Element in a BST.

    Iterative inorder traversal (sorted order in a BST), decrementing k
    at each visited node and halting the moment it reaches zero. The
    stack version is preferred precisely because it can stop
    mid-traversal: O(h + k) instead of walking the whole tree. O(h)
    space.
    """
    pending: list[TreeNode] = []
    node = root
    while node or pending:
        while node:
            pending.append(node)
            node = node.left
        node = pending.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right
    raise ValueError("k exceeds tree size")

// LC 230. Iterative inorder visits BST values in sorted order; halting at the
// kth pop costs O(h + k) instead of walking the whole tree.
int kthSmallest(TreeNode* root, int k) {
    vector<TreeNode*> stack;
    TreeNode* node = root;
    while (node || !stack.empty()) {
        while (node) {
            stack.push_back(node);
            node = node->left;
        }
        node = stack.back();
        stack.pop_back();
        if (--k == 0) return node->val;
        node = node->right;
    }
    return -1;  // unreachable: constraints guarantee k <= tree size
}

/// LC 230. Iterative inorder that halts at the kth pop: O(h + k) instead of
/// walking the whole tree.
pub fn kth_smallest(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
    let mut stack: Vec<Rc<RefCell<TreeNode>>> = Vec::new();
    let mut current = root;
    let mut k = k;
    loop {
        while let Some(node) = current {
            current = node.borrow().left.clone();
            stack.push(node);
        }
        let node = stack.pop().unwrap();
        k -= 1;
        if k == 0 {
            return node.borrow().val;
        }
        current = node.borrow().right.clone();
    }
}

/** LC 230. Iterative inorder visits BST values in sorted order; halt at the kth pop, O(h + k). */
export function kthSmallest(root: TreeNode | null, k: number): number {
  const stack: TreeNode[] = [];
  let node = root;
  while (node !== null || stack.length > 0) {
    while (node !== null) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop()!;
    if (--k === 0) return node.val;
    node = node.right;
  }
  return -1; // unreachable for valid k
}

// LC 230. Iterative inorder visits BST values in sorted order; halting at the
// kth pop costs O(h + k) instead of walking the whole tree.
func kthSmallest(root *TreeNode, k int) int {
	var stack []*TreeNode
	node := root
	for node != nil || len(stack) > 0 {
		for node != nil {
			stack = append(stack, node)
			node = node.Left
		}
		node = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		k--
		if k == 0 {
			return node.Val
		}
		node = node.Right
	}
	return -1 // unreachable: constraints guarantee k <= tree size
}

// LC 230. Iterative inorder visits BST values in sorted order; halting at the
// kth pop costs O(h + k) instead of walking the whole tree.
func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
    var stack: [TreeNode] = []
    var node = root
    var remaining = k
    while node != nil || !stack.isEmpty {
        while let current = node {
            stack.append(current)
            node = current.left
        }
        let visited = stack.removeLast()
        remaining -= 1
        if remaining == 0 { return visited.val }
        node = visited.right
    }
    return -1  // unreachable: constraints guarantee k <= tree size
}

def build_tree(preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
    """LC 105. Construct Binary Tree from Preorder and Inorder Traversal.

    The first preorder element is always the root; its position in
    inorder splits everything into left and right subtrees. A
    value-to-index map over inorder kills the linear search per node,
    and a single advancing preorder index replaces array slicing --
    together they take the build from O(n^2) to O(n). O(n) space.
    """
    inorder_index = {val: i for i, val in enumerate(inorder)}
    next_root = 0  # index of the next preorder value to consume

    def build(lo: int, hi: int) -> Optional[TreeNode]:
        nonlocal next_root
        if lo > hi:
            return None
        root = TreeNode(preorder[next_root])
        next_root += 1
        split = inorder_index[root.val]
        # left subtree must be built first: preorder lists it before the right
        root.left = build(lo, split - 1)
        root.right = build(split + 1, hi)
        return root

    return build(0, len(inorder) - 1)

// LC 105. The first preorder element is always the root, and its inorder
// position splits the left and right subtrees. A value->index map over
// inorder plus a shared preorder cursor (preorder lists the entire left
// subtree before the right) takes the build from O(n^2) to O(n).
TreeNode* buildTree(vector<int> preorder, vector<int> inorder) {
    unordered_map<int, int> indexInInorder;
    for (int i = 0; i < static_cast<int>(inorder.size()); ++i) indexInInorder[inorder[i]] = i;
    int cursor = 0;  // next root in preorder
    auto build = [&](auto&& self, int lo, int hi) -> TreeNode* {  // inorder slice [lo, hi]
        if (lo > hi) return nullptr;
        TreeNode* node = new TreeNode(preorder[cursor++]);
        int mid = indexInInorder[node->val];
        node->left = self(self, lo, mid - 1);
        node->right = self(self, mid + 1, hi);
        return node;
    };
    return build(build, 0, static_cast<int>(inorder.size()) - 1);
}

/// LC 105. First preorder element is the root; a value-to-index map over
/// inorder splits left/right slices without a linear search, giving O(n).
pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
    fn build(
        preorder: &[i32],
        index: &HashMap<i32, usize>,
        cursor: &mut usize,
        lo: usize,
        hi: usize, // inorder window [lo, hi)
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if lo >= hi {
            return None;
        }
        let val = preorder[*cursor];
        *cursor += 1;
        let mid = index[&val];
        let left = build(preorder, index, cursor, lo, mid);
        let right = build(preorder, index, cursor, mid + 1, hi);
        Some(Rc::new(RefCell::new(TreeNode { val, left, right })))
    }
    let index: HashMap<i32, usize> = inorder.iter().enumerate().map(|(i, &v)| (v, i)).collect();
    let mut cursor = 0;
    let n = inorder.len();
    build(&preorder, &index, &mut cursor, 0, n)
}

/** LC 105. Preorder's front is always the next root; an inorder index map splits the slices in O(1). */
export function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  const inorderIndex = new Map<number, number>();
  inorder.forEach((val, i) => inorderIndex.set(val, i));
  let pre = 0; // next root in preorder; advances once per built node
  function build(lo: number, hi: number): TreeNode | null {
    if (lo > hi) return null;
    const root = new TreeNode(preorder[pre++]);
    const mid = inorderIndex.get(root.val)!;
    root.left = build(lo, mid - 1); // left first, so `pre` consumes preorder in order
    root.right = build(mid + 1, hi);
    return root;
  }
  return build(0, inorder.length - 1);
}

// LC 105. The first preorder element is always the root, and its inorder
// position splits the subtrees; a value->index map plus a shared preorder
// cursor take the build from O(n^2) to O(n).
func buildTree(preorder []int, inorder []int) *TreeNode {
	indexInInorder := make(map[int]int, len(inorder))
	for i, v := range inorder {
		indexInInorder[v] = i
	}
	cursor := 0 // next root in preorder
	var build func(lo, hi int) *TreeNode
	build = func(lo, hi int) *TreeNode { // inorder slice [lo, hi]
		if lo > hi {
			return nil
		}
		node := &TreeNode{Val: preorder[cursor]}
		cursor++
		mid := indexInInorder[node.Val]
		node.Left = build(lo, mid-1) // left first: preorder lists it before the right
		node.Right = build(mid+1, hi)
		return node
	}
	return build(0, len(inorder)-1)
}

// LC 105. The first preorder element is always the root, and its inorder
// position splits the left and right subtrees. A value-to-index map plus a
// shared preorder cursor takes the build from O(n^2) to O(n).
func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
    var indexInInorder: [Int: Int] = [:]
    for (i, value) in inorder.enumerated() { indexInInorder[value] = i }
    var cursor = 0  // next root in preorder
    func build(_ lo: Int, _ hi: Int) -> TreeNode? {  // inorder slice [lo, hi]
        if lo > hi { return nil }
        let node = TreeNode(preorder[cursor])
        cursor += 1
        let mid = indexInInorder[node.val]!
        node.left = build(lo, mid - 1)  // left first: preorder lists it before the right
        node.right = build(mid + 1, hi)
        return node
    }
    return build(0, inorder.count - 1)
}

def rob_tree(root: Optional[TreeNode]) -> int:
    """LC 337. House Robber III.

    Postorder DFS returning a (rob, skip) pair per node: rob adds the
    node's value to both children's SKIP results; skip takes the max of
    each child's pair. The subtle point: skipping a node does not force
    robbing its children, so skip uses each child's best of both
    states. O(n) time, O(h) stack.
    """

    def best_pair(node: Optional[TreeNode]) -> tuple[int, int]:
        if not node:
            return 0, 0
        left_rob, left_skip = best_pair(node.left)
        right_rob, right_skip = best_pair(node.right)
        rob = node.val + left_skip + right_skip
        skip = max(left_rob, left_skip) + max(right_rob, right_skip)
        return rob, skip

    return max(best_pair(root))

// LC 337. Postorder pair (rob, skip) per node: rob adds the node's value to
// both children's skip results; skip takes each child's BEST of both states,
// since skipping a parent does not force robbing its children.
int robTree(TreeNode* root) {
    auto dfs = [&](auto&& self, TreeNode* node) -> pair<int, int> {  // (rob, skip)
        if (!node) return {0, 0};
        auto [robLeft, skipLeft] = self(self, node->left);
        auto [robRight, skipRight] = self(self, node->right);
        int rob = node->val + skipLeft + skipRight;
        int skip = max(robLeft, skipLeft) + max(robRight, skipRight);
        return {rob, skip};
    };
    auto [rob, skip] = dfs(dfs, root);
    return max(rob, skip);
}

/// LC 337. Postorder (rob, skip) pair per node. Subtle point: skip does NOT
/// force robbing the children, so it takes each child's best of both states.
pub fn rob_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>) -> (i32, i32) {
        match node {
            None => (0, 0),
            Some(rc) => {
                let n = rc.borrow();
                let (left_rob, left_skip) = dfs(&n.left);
                let (right_rob, right_skip) = dfs(&n.right);
                let rob = n.val + left_skip + right_skip;
                let skip = left_rob.max(left_skip) + right_rob.max(right_skip);
                (rob, skip)
            }
        }
    }
    let (rob, skip) = dfs(&root);
    rob.max(skip)
}

/** LC 337. Postorder returns [rob, skip] per node; skip takes each child's BEST, not its skip. */
export function robTree(root: TreeNode | null): number {
  function best(node: TreeNode | null): [number, number] {
    if (!node) return [0, 0];
    const [robLeft, skipLeft] = best(node.left);
    const [robRight, skipRight] = best(node.right);
    const rob = node.val + skipLeft + skipRight;
    // skipping a parent does not force robbing its children
    const skip = Math.max(robLeft, skipLeft) + Math.max(robRight, skipRight);
    return [rob, skip];
  }
  return Math.max(...best(root));
}

// LC 337. Postorder (rob, skip) pair per node: rob adds the node's value to
// both children's skip results; skip takes each child's BEST of both states.
func robTree(root *TreeNode) int {
	var dfs func(node *TreeNode) (int, int)
	dfs = func(node *TreeNode) (int, int) { // (rob, skip)
		if node == nil {
			return 0, 0
		}
		robLeft, skipLeft := dfs(node.Left)
		robRight, skipRight := dfs(node.Right)
		bestLeft, bestRight := robLeft, robRight
		if skipLeft > bestLeft {
			bestLeft = skipLeft
		}
		if skipRight > bestRight {
			bestRight = skipRight
		}
		return node.Val + skipLeft + skipRight, bestLeft + bestRight
	}
	rob, skip := dfs(root)
	if rob > skip {
		return rob
	}
	return skip
}

// LC 337. Postorder (rob, skip) pair per node: rob adds the node's value to
// both children's skip results; skip takes each child's BEST of both states.
func robTree(_ root: TreeNode?) -> Int {
    func bestPair(_ node: TreeNode?) -> (rob: Int, skip: Int) {
        guard let node = node else { return (0, 0) }
        let left = bestPair(node.left)
        let right = bestPair(node.right)
        let rob = node.val + left.skip + right.skip
        let skip = max(left.rob, left.skip) + max(right.rob, right.skip)
        return (rob, skip)
    }
    let best = bestPair(root)
    return max(best.rob, best.skip)
}

def remove_leaf_nodes(root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
    """LC 1325. Delete Leaves With a Given Value.

    Postorder: recurse into both children FIRST, reassigning each child
    pointer to the recursive result, then return None if the current
    node has become a target-valued leaf. Judging a node only after its
    subtree settles is what lets deletions cascade upward. O(n) time,
    O(h) stack.
    """
    if not root:
        return None
    root.left = remove_leaf_nodes(root.left, target)
    root.right = remove_leaf_nodes(root.right, target)
    if not root.left and not root.right and root.val == target:
        return None  # became a target leaf only after its children were judged
    return root

// LC 1325. Postorder: reassign each child pointer to the recursive result
// FIRST, then return null if the node is now a target-valued leaf. Judging a
// node only after its subtree settles is what lets deletions cascade upward.
TreeNode* removeLeafNodes(TreeNode* root, int target) {
    if (!root) return nullptr;
    root->left = removeLeafNodes(root->left, target);
    root->right = removeLeafNodes(root->right, target);
    if (!root->left && !root->right && root->val == target) return nullptr;
    return root;
}

/// LC 1325. Postorder: reassign both child pointers to the recursive result
/// FIRST, then judge the node -- deletions cascade upward, so a node is only
/// a leaf candidate after its subtree settles.
pub fn remove_leaf_nodes(
    root: Option<Rc<RefCell<TreeNode>>>,
    target: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
    let node = root?;
    {
        let mut n = node.borrow_mut();
        let left = n.left.take();
        n.left = remove_leaf_nodes(left, target);
        let right = n.right.take();
        n.right = remove_leaf_nodes(right, target);
    }
    let now_target_leaf = {
        let n = node.borrow();
        n.left.is_none() && n.right.is_none() && n.val == target
    };
    if now_target_leaf { None } else { Some(node) }
}

/** LC 1325. Postorder: rewire each child to the recursive result first, THEN judge this node. */
export function removeLeafNodes(root: TreeNode | null, target: number): TreeNode | null {
  if (!root) return null;
  root.left = removeLeafNodes(root.left, target);
  root.right = removeLeafNodes(root.right, target);
  // deletions cascade upward: a node is judged only after its subtree settles
  if (!root.left && !root.right && root.val === target) return null;
  return root;
}

// LC 1325. Postorder: reassign each child pointer to the recursive result
// FIRST, then return nil if the node is now a target-valued leaf, so
// deletions cascade upward.
func removeLeafNodes(root *TreeNode, target int) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left = removeLeafNodes(root.Left, target)
	root.Right = removeLeafNodes(root.Right, target)
	if root.Left == nil && root.Right == nil && root.Val == target {
		return nil
	}
	return root
}

// LC 1325. Postorder: reassign each child pointer to the recursive result
// FIRST, then return nil if the node is now a target-valued leaf, so
// deletions cascade upward.
func removeLeafNodes(_ root: TreeNode?, _ target: Int) -> TreeNode? {
    guard let root = root else { return nil }
    root.left = removeLeafNodes(root.left, target)
    root.right = removeLeafNodes(root.right, target)
    if root.left == nil && root.right == nil && root.val == target {
        return nil  // became a target leaf only after its children were judged
    }
    return root
}

def max_path_sum(root: Optional[TreeNode]) -> int:
    """LC 124. Binary Tree Maximum Path Sum.

    DFS returns each node's best DOWNWARD sum (one arm, at most one
    child) while a nonlocal best collects the BEND: node value plus both
    children's arms. Clamping each child's contribution at zero is the
    key -- negative branches are better dropped -- but the bend itself
    may stay negative when every node is. O(n) time, O(h) stack.
    """
    path_best = float("-inf")

    def best_arm(node: Optional[TreeNode]) -> int:
        nonlocal path_best
        if not node:
            return 0
        left = max(best_arm(node.left), 0)  # a negative arm contributes nothing
        right = max(best_arm(node.right), 0)
        path_best = max(path_best, node.val + left + right)
        return node.val + max(left, right)

    best_arm(root)
    return int(path_best)

// LC 124. DFS returns each node's best DOWNWARD arm (node plus at most one
// child) while a global best collects the bend: node value plus both arms.
// Clamping each child's contribution at zero is the key, since negative
// branches are better dropped entirely.
int maxPathSum(TreeNode* root) {
    int best = INT_MIN;
    auto arm = [&](auto&& self, TreeNode* node) -> int {
        if (!node) return 0;
        int left = max(0, self(self, node->left));    // negative branch: drop it
        int right = max(0, self(self, node->right));
        best = max(best, node->val + left + right);   // path bends at this node
        return node->val + max(left, right);          // an arm continues one way only
    };
    arm(arm, root);
    return best;
}

/// LC 124. Return the best downward arm (at most one child), collect the
/// best bend (node + both arms) in a shared maximum. Clamp each child's
/// contribution at zero: negative branches are better dropped.
pub fn max_path_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    fn arm(node: &Option<Rc<RefCell<TreeNode>>>, best: &mut i32) -> i32 {
        match node {
            None => 0,
            Some(rc) => {
                let n = rc.borrow();
                let left = arm(&n.left, best).max(0);
                let right = arm(&n.right, best).max(0);
                *best = (*best).max(n.val + left + right);
                n.val + left.max(right)
            }
        }
    }
    let mut best = i32::MIN;
    arm(&root, &mut best);
    best
}

/** LC 124. DFS returns the best single downward arm; a shared max collects the bend at each node. */
export function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;
  function arm(node: TreeNode | null): number {
    if (!node) return 0;
    const left = Math.max(arm(node.left), 0); // negative branches are better dropped
    const right = Math.max(arm(node.right), 0);
    best = Math.max(best, node.val + left + right); // the bend uses both arms but cannot extend upward
    return node.val + Math.max(left, right);
  }
  arm(root);
  return best;
}

// LC 124. DFS returns each node's best DOWNWARD arm (node plus at most one
// child) while a captured best collects the bend: node value plus both arms,
// each clamped at zero since negative branches are better dropped.
func maxPathSum(root *TreeNode) int {
	best := math.MinInt32
	var arm func(node *TreeNode) int
	arm = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		left := arm(node.Left)
		if left < 0 {
			left = 0 // negative branch: drop it
		}
		right := arm(node.Right)
		if right < 0 {
			right = 0
		}
		if bend := node.Val + left + right; bend > best {
			best = bend // path bends at this node
		}
		if left > right {
			return node.Val + left // an arm continues one way only
		}
		return node.Val + right
	}
	arm(root)
	return best
}

// LC 124. DFS returns each node's best DOWNWARD arm (node plus at most one
// child) while a captured best collects the bend: node value plus both arms.
// Clamping each child's contribution at zero drops negative branches.
func maxPathSum(_ root: TreeNode?) -> Int {
    var best = Int.min
    func bestArm(_ node: TreeNode?) -> Int {
        guard let node = node else { return 0 }
        let left = max(bestArm(node.left), 0)  // a negative arm contributes nothing
        let right = max(bestArm(node.right), 0)
        best = max(best, node.val + left + right)  // path bends at this node
        return node.val + max(left, right)  // an arm continues one way only
    }
    _ = bestArm(root)
    return best
}

class Codec:
    """LC 297. Serialize and Deserialize Binary Tree.

    Serialize with preorder DFS, writing each value and a '#' marker at
    every null; the explicit null markers make one preorder pass
    unambiguous. Deserialize consumes tokens in the same order, building
    a node and then recursively its left and right subtrees. O(n) time
    and space both ways.
    """

    def serialize(self, root: Optional[TreeNode]) -> str:
        tokens: list[str] = []

        def write(node: Optional[TreeNode]) -> None:
            if not node:
                tokens.append("#")
                return
            tokens.append(str(node.val))
            write(node.left)
            write(node.right)

        write(root)
        return ",".join(tokens)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        tokens = iter(data.split(","))

        def read() -> Optional[TreeNode]:
            token = next(tokens)
            if token == "#":
                return None
            node = TreeNode(int(token))
            node.left = read()  # preorder: left subtree's tokens come next
            node.right = read()
            return node

        return read()

// LC 297. Preorder with a '#' marker at every null makes a single pass
// unambiguous; deserialize consumes tokens in the same order, building each
// node and then recursively its left and right subtrees.
class Codec {
   public:
    string serialize(TreeNode* root) {
        string out;
        auto dfs = [&](auto&& self, TreeNode* node) -> void {
            if (!node) {
                out += "#,";
                return;
            }
            out += to_string(node->val) + ",";
            self(self, node->left);
            self(self, node->right);
        };
        dfs(dfs, root);
        return out;
    }
    TreeNode* deserialize(string data) {
        stringstream tokens(data);
        auto dfs = [&](auto&& self) -> TreeNode* {
            string token;
            getline(tokens, token, ',');
            if (token == "#") return nullptr;
            TreeNode* node = new TreeNode(stoi(token));
            node->left = self(self);
            node->right = self(self);
            return node;
        };
        return dfs(dfs);
    }
};

/// LC 297. Preorder with explicit "#" null markers makes one pass
/// unambiguous; deserialize consumes tokens in the same order it wrote them.
pub struct Codec;

impl Codec {
    pub fn new() -> Self {
        Codec
    }

    pub fn serialize(&self, root: Option<Rc<RefCell<TreeNode>>>) -> String {
        fn write(node: &Option<Rc<RefCell<TreeNode>>>, out: &mut Vec<String>) {
            match node {
                None => out.push("#".to_string()),
                Some(rc) => {
                    let n = rc.borrow();
                    out.push(n.val.to_string());
                    write(&n.left, out);
                    write(&n.right, out);
                }
            }
        }
        let mut out = Vec::new();
        write(&root, &mut out);
        out.join(",")
    }

    pub fn deserialize(&self, data: String) -> Option<Rc<RefCell<TreeNode>>> {
        fn read<'a, I: Iterator<Item = &'a str>>(tokens: &mut I) -> Option<Rc<RefCell<TreeNode>>> {
            let token = tokens.next()?;
            if token == "#" {
                return None;
            }
            let val = token.parse().unwrap();
            let left = read(tokens);
            let right = read(tokens);
            Some(Rc::new(RefCell::new(TreeNode { val, left, right })))
        }
        read(&mut data.split(','))
    }
}

impl Codec {
    pub fn new() -> Self {
        Codec
    }

    pub fn serialize(&self, root: Option<Rc<RefCell<TreeNode>>>) -> String {
        fn write(node: &Option<Rc<RefCell<TreeNode>>>, out: &mut Vec<String>) {
            match node {
                None => out.push("#".to_string()),
                Some(rc) => {
                    let n = rc.borrow();
                    out.push(n.val.to_string());
                    write(&n.left, out);
                    write(&n.right, out);
                }
            }
        }
        let mut out = Vec::new();
        write(&root, &mut out);
        out.join(",")
    }

    pub fn deserialize(&self, data: String) -> Option<Rc<RefCell<TreeNode>>> {
        fn read<'a, I: Iterator<Item = &'a str>>(tokens: &mut I) -> Option<Rc<RefCell<TreeNode>>> {
            let token = tokens.next()?;
            if token == "#" {
                return None;
            }
            let val = token.parse().unwrap();
            let left = read(tokens);
            let right = read(tokens);
            Some(Rc::new(RefCell::new(TreeNode { val, left, right })))
        }
        read(&mut data.split(','))
    }
}

/** LC 297. Preorder with explicit '#' null markers makes one pass unambiguous; deserialize replays it. */
export class Codec {
  serialize(root: TreeNode | null): string {
    const tokens: string[] = [];
    function write(node: TreeNode | null): void {
      if (!node) {
        tokens.push("#"); // without null markers one traversal cannot pin down the structure
        return;
      }
      tokens.push(String(node.val));
      write(node.left);
      write(node.right);
    }
    write(root);
    return tokens.join(",");
  }

  deserialize(data: string): TreeNode | null {
    const tokens = data.split(",");
    let i = 0; // consume tokens strictly left to right, mirroring serialize
    function read(): TreeNode | null {
      const token = tokens[i++];
      if (token === "#") return null;
      const node = new TreeNode(Number(token));
      node.left = read();
      node.right = read();
      return node;
    }
    return read();
  }
}

// LC 297. Preorder with a '#' marker at every null makes one pass
// unambiguous; deserialize consumes tokens in the same order, building each
// node and then recursively its left and right subtrees.
type Codec struct{}

func newCodec() Codec {
	return Codec{}
}

func (c Codec) serialize(root *TreeNode) string {
	var tokens []string
	var write func(node *TreeNode)
	write = func(node *TreeNode) {
		if node == nil {
			tokens = append(tokens, "#")
			return
		}
		tokens = append(tokens, strconv.Itoa(node.Val))
		write(node.Left)
		write(node.Right)
	}
	write(root)
	return strings.Join(tokens, ",")
}

func (c Codec) deserialize(data string) *TreeNode {
	tokens := strings.Split(data, ",")
	next := 0
	var read func() *TreeNode
	read = func() *TreeNode {
		token := tokens[next]
		next++
		if token == "#" {
			return nil
		}
		val, _ := strconv.Atoi(token)
		node := &TreeNode{Val: val}
		node.Left = read() // preorder: left subtree's tokens come next
		node.Right = read()
		return node
	}
	return read()
}

// LC 297. Preorder with a '#' marker at every null makes a single pass
// unambiguous; deserialize consumes tokens in the same order, building each
// node and then recursively its left and right subtrees.
class Codec {
    func serialize(_ root: TreeNode?) -> String {
        var tokens: [String] = []
        func write(_ node: TreeNode?) {
            guard let node = node else {
                tokens.append("#")
                return
            }
            tokens.append(String(node.val))
            write(node.left)
            write(node.right)
        }
        write(root)
        return tokens.joined(separator: ",")
    }
    func deserialize(_ data: String) -> TreeNode? {
        let tokens = data.split(separator: ",", omittingEmptySubsequences: false)
        var cursor = 0
        func read() -> TreeNode? {
            let token = tokens[cursor]
            cursor += 1
            if token == "#" { return nil }
            let node = TreeNode(Int(token)!)
            node.left = read()  // preorder: left subtree's tokens come next
            node.right = read()
            return node
        }
        return read()
    }
}