Trees and Binary Search Trees Questions

Conventions first
I would define height as the number of edges on the longest path from a node to a leaf. That makes an empty tree height -1 and a leaf height 0. I would define depth as the number of edges from the root to a node, so the root has depth 0. That keeps the API consistent.

def tree_height(root):
    if root is None:
        return -1
    return 1 + max(tree_height(root.left), tree_height(root.right))


def node_depth(root, target):
    def dfs(node, depth):
        if node is None:
            return None
        if node is target:
            return depth
        left = dfs(node.left, depth + 1)
        if left is not None:
            return left
        return dfs(node.right, depth + 1)

    return dfs(root, 0)

Worked example
If the tree is 10 -> 4 -> 2, then tree_height(root) is 2, node_depth(root, 10) is 0, and node_depth(root, 2) is 2.

API design choice
I would return None if the target node is not present, rather than guessing. That makes the behavior explicit and avoids ambiguity.

Approach (brief): Use a post-order DFS that for each node computes the maximum gain we can obtain by a path starting at that node and going down (to either left or right). While visiting a node we also consider the best path that passes through the node (left_gain + node.val + right_gain) and keep a global maximum. Using max(0, child_gain) lets us ignore negative child contributions unless all values are negative — the global max initialized to -inf ensures the largest node is still returned.

# Python implementation of max_path_sum for a binary tree
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_path_sum(root):
    """
    Returns the maximum sum of values along any path in the tree.
    Path may start and end at any nodes.
    """
    import math
    best = -math.inf  # global maximum path sum

    def dfs(node):
        nonlocal best
        if node is None:
            return 0
        # Post-order: compute left and right gains first
        left_gain = max(0, dfs(node.left))   # ignore negative contributions
        right_gain = max(0, dfs(node.right))
        # Path passing through node uses both children
        current = node.val + left_gain + right_gain
        best = max(best, current)
        # Return max gain for parent to use (only one branch can be extended)
        return node.val + max(left_gain, right_gain)

    dfs(root)
    return best

Key points / correctness (post-order reasoning):

• Post-order ensures child gains are available before processing the parent.
• For each node, we compute:
  • left_gain = max(0, best path down left subtree starting at left child)
  • right_gain = similarly for right
  • candidate path through node = node.val + left_gain + right_gain (covers paths that pass through this node)
  • update global best with candidate
  • return node.val + max(left_gain, right_gain) as the best extendable path upward (can't extend both branches upward).
• Using max(0, ...) avoids dragging down sums with negative children; initializing best to -inf ensures correct result for all-negative trees (global becomes max single node).

Time complexity: O(n) — each node visited once.
Space complexity: O(h) recursion stack where h is tree height (O(n) worst-case, O(log n) for balanced).

Edge cases:

• Empty tree: returns -inf in this code; if desired, you can return 0 or None — clarify spec.
• All-negative nodes: handled — returns the largest single node value.
• Very deep trees: may need iterative DFS or increase recursion limit.

Approach: compute total sum with one DFS, then a second DFS (or same traversal) to collect all subtree sums. If any subtree sum equals total_sum - subtree_sum (i.e., total_sum == 2 * subtree_sum) and the subtree is not the whole tree, removing the edge above that subtree partitions tree into equal sums. Use a post-order traversal to compute subtree sums and store them in a hash set. O(n) time, O(n) space.

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

def can_partition_equal_sum(root: TreeNode) -> bool:
    """
    Returns True if removing exactly one edge splits the tree into two trees
    with equal sum of node values.
    """
    if not root:
        return False

    subtree_sums = []
    # post-order DFS to compute subtree sums
    def dfs(node):
        if not node:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        s = node.val + left + right
        subtree_sums.append(s)
        return s

    total = dfs(root)
    # remove full-tree sum from consideration (can't cut above root)
    subtree_sums.pop()  # last appended is total sum
    # check if any subtree sum equals half of total
    if total % 2 != 0:
        return False
    half = total // 2
    return half in subtree_sums

Key points:

• Single traversal computes all subtree sums (post-order); collecting sums adds O(n) space.
• Time: O(n) visiting each node once. Space: O(n) for recursion stack + list/set.
• Edge cases: empty tree -> False; single node -> False (no edge to remove); negative values handled fine.
• Integer overflow: Python ints are arbitrary precision so no problem. In languages like C++/Java, use 64-bit (long/long long) and beware of sums exceeding 64-bit — consider bigints or check for overflow when values or node counts are huge.
• Relation to ML systems: this is analogous to partitioning compute graphs or resource allocation in ML pipelines — splitting a computation graph at an edge to balance compute or memory (equal-weight partitioning), or sharding feature trees/decision graphs. Subtree-sum logic maps to computing resource cost per subgraph; efficient single-pass aggregation and careful numeric handling are critical in production ML systems.

Approach: use a queue (collections.deque) to perform BFS. For each level, record current queue length, pop that many nodes to form the level list, and push children. This is explicit-queue BFS with O(n) time and O(w) space (w = max width).

from collections import deque
from typing import List, Optional

class TreeNode:
    def __init__(self, val: int, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right

def level_order(root: Optional[TreeNode]) -> List[List[int]]:
    """
    Return list of levels, each a list of node values (breadth-first).
    Time: O(n). Space: O(w) where w is max width (queue).
    """
    if not root:
        return []
    q = deque([root])
    result = []
    while q:
        level_size = len(q)
        level_vals = []
        for _ in range(level_size):
            node = q.popleft()
            level_vals.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(level_vals)
    return result

Key points:

• Uses explicit queue (deque) and processes nodes level-by-level.
• Time O(n): each node visited once. Space O(w): queue holds at most one level (max width).

Edge cases:

• Empty tree (returns []).
• Unbalanced trees (width determines peak memory).
• Single-node or skewed trees handled naturally.

Why level-order serialization for checkpointing tree-based models:

• Preserves tree structure by depth, making reconstruction simple and deterministic.
• Compact and sequential format suitable for streaming and incremental saves.
• Facilitates parallel loading/saving by level and efficient partial checkpoints (useful for large ensembles or boosting trees).

Approach: choose the middle element as root recursively so left/right subarrays differ by at most one element — this produces a height-balanced BST. This visits each element exactly once, so O(n) time.

# python
from typing import List, Optional

class TreeNode:
    def __init__(self, val:int, left:Optional['TreeNode']=None, right:Optional['TreeNode']=None):
        self.val = val
        self.left = left
        self.right = right

def sorted_array_to_bst(nums: List[int]) -> Optional[TreeNode]:
    """Convert sorted unique integers to a height-balanced BST in O(n) time (each element visited once)."""
    def build(l: int, r: int) -> Optional[TreeNode]:
        if l > r:
            return None
        mid = (l + r) // 2               # choose middle (left-middle on even length)
        root = TreeNode(nums[mid])
        root.left = build(l, mid - 1)
        root.right = build(mid + 1, r)
        return root

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

Recursion invariant: for any call build(l,r), it returns a BST that contains exactly nums[l..r], is height-balanced (sizes of left/right subtrees differ by ≤1), and preserves BST order. Choosing mid maintains the invariant for subcalls.

Expected height: for n nodes the minimal achievable height is floor(log2 n). Recursion depth is O(log n). Complexity: Time O(n), Space O(n) for nodes plus O(log n) call stack. Edge cases: empty array -> None; handles even/odd lengths and single element.