Trees and Binary Search Trees Questions

Approach: Keep two heaps: a max-heap L containing the k smallest elements (largest at top) and a min-heap R containing the rest. Maintain |L| = k (or smaller if total < k). Use lazy deletion via a dictionary to handle high-throughput deletions efficiently (mark-and-clean) to avoid O(n) removals. This gives low latency per operation and bounded memory proportional to number of active elements.

import heapq
from collections import Counter

class KthSmallest:
    def __init__(self, k):
        self.k = k
        self.L = []  # max-heap (store negatives)
        self.R = []  # min-heap
        self.del_counts = Counter()  # lazy deletions
        self.size = 0

    def _clean(self, heap, is_max):
        while heap:
            val = -heap[0] if is_max else heap[0]
            if self.del_counts[val] > 0:
                heapq.heappop(heap)
                self.del_counts[val] -= 1
            else:
                break

    def _rebalance(self):
        # ensure L has min(k, size) elements
        while len(self.L) > min(self.k, self.size):
            self._clean(self.L, True)
            if not self.L:
                break
            val = -heapq.heappop(self.L)
            heapq.heappush(self.R, val)
        while len(self.L) < min(self.k, self.size) and self.R:
            self._clean(self.R, False)
            if not self.R:
                break
            val = heapq.heappop(self.R)
            heapq.heappush(self.L, -val)

    def insert(self, x):
        self.size += 1
        if self.L and x <= -self.L[0]:
            heapq.heappush(self.L, -x)
        else:
            heapq.heappush(self.R, x)
        self._rebalance()

    def delete(self, x):
        # lazy: mark for deletion if present
        if self.size == 0:
            return False
        # attempt to decide which heap x likely is in by comparing to L top
        if self.L and x <= -self.L[0]:
            # mark deletion and decrement size; actual pop happens in _clean
            self.del_counts[x] += 1
            self.size -= 1
        else:
            self.del_counts[x] += 1
            self.size -= 1
        self._clean(self.L, True)
        self._clean(self.R, False)
        self._rebalance()
        return True

    def kth(self):
        if self.size < self.k:
            return None
        self._clean(self.L, True)
        return -self.L[0] if self.L else None

Key concepts:

• Use two heaps to get O(1) kth query (top of L) and O(log n) amortized insert.
• Lazy deletion avoids costly heap removals; periodic cleaning happens on access.

Complexity:

• Insert: O(log n) worst-case (heap push + rebalance)
• Delete: O(1) to mark, plus amortized O(log n) when cleaning; worst-case more if many stale entries accumulate
• kth: O(1) after cleaning
• Space: O(n) plus counters

Trade-offs vs order-statistic BST:

• OST (augmented balanced BST) supports exact delete in O(log n) and exact k-th retrieval in O(log n). It uses more complex code and pointer-heavy memory, potential higher memory per node and harder to implement in some languages/environments.
• Heaps + lazy deletion are simpler, often faster in practice (lower constants), and better for high-throughput streams where deletions are frequent but exact immediate removal is not required. However, lazy approach can accumulate tombstones (addresses with periodic compaction needed) and worst-case latency spikes during heavy cleanup. An OST gives more predictable per-op latency and no tombstone growth but higher implementation and memory cost. For SRE, prefer heaps if simplicity and operational robustness matter; choose OST if strict worst-case latency and memory bounds are required.

Approach: do a post-order traversal so children are processed before parent. When a node is a leaf, append it to a doubly-linked list using its left/right as prev/next and return None to the caller so the leaf is removed from the tree. Use recursion so auxiliary space is O(h) (call stack). Maintain head and tail pointers for the DLL.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left   # used as prev in DLL
        self.right = right # used as next in DLL

def leaves_to_dll(root: TreeNode) -> TreeNode:
    """
    Convert tree leaves into a doubly-linked list (left=prev, right=next)
    in left-to-right order. Remove leaves from the tree. Return head of DLL.
    O(n) time, O(h) auxiliary space.
    """
    head = None
    tail = None

    def dfs(node):
        nonlocal head, tail
        if node is None:
            return None
        # if leaf, append to DLL and remove from tree by returning None
        if node.left is None and node.right is None:
            node.left = tail  # prev
            node.right = None
            if tail:
                tail.right = node
            else:
                head = node
            tail = node
            return None
        # post-order: process left then right so DLL is left-to-right
        node.left = dfs(node.left)
        node.right = dfs(node.right)
        return node

    dfs(root)
    return head

Key points:

• Post-order ensures left-to-right ordering for leaves.
• We reuse node.left/node.right as prev/next; no new nodes for leaves.
• Returning None from dfs removes the leaf from its parent.
  Time: O(n) visiting each node once. Auxiliary space: O(h) call stack.
  Edge cases: root None -> returns None; single-node tree -> that node becomes head (and tree becomes empty). Alternative: iterative post-order using an explicit stack if recursion depth is a concern.

Two safe approaches: (A) recursive min/max bounds, and (B) iterative inorder traversal. Recursive is straightforward and intuitive; iterative inorder is stack-based and avoids recursion-depth limits (important for very deep skewed trees in SRE contexts).

Approach A — Recursive bounds:

• Pass down allowed (low, high) exclusive bounds. For node, require low < node.val < high.
• Recurse left with (low, node.val) and right with (node.val, high).
• Use float("-inf") and float("inf") or None for initial bounds.

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

def is_valid_bst_recursive(root: TreeNode) -> bool:
    def helper(node, low, high):
        if node is None:
            return True
        val = node.val
        if not (low < val < high):
            return False
        return helper(node.left, low, val) and helper(node.right, val, high)
    return helper(root, float("-inf"), float("inf"))

Correctness: Each node enforces global constraints from ancestors, so nodes in right subtree must be > ancestor values, not just parent.

Complexity: O(n) time, O(h) recursion stack space (h = tree height). Risk: recursion depth O(n) on skewed tree may hit Python recursion limit.

Approach B — Iterative inorder (preferred for deep trees):

• Inorder of BST yields strictly increasing sequence when duplicates not allowed.
• Use an explicit stack, track previous value, ensure current > prev.

# python
def is_valid_bst_iterative(root: TreeNode) -> bool:
    stack = []
    node = root
    prev = float("-inf")
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if node.val <= prev:
            return False
        prev = node.val
        node = node.right
    return True

Complexity: O(n) time, O(h) space (stack). Iterative avoids recursion limits and is robust for very deep skewed trees.

Edge cases:

• Empty tree -> True.
• Single node -> True.
• Duplicates -> must return False; both methods use strict comparisons.
• Very deep skewed tree -> use iterative to avoid recursion limits or increase recursion limit carefully.

Recommendation for SRE: use iterative inorder in production probes/parsers to avoid stack overflow; add input validation and defensive checks for malformed nodes.

To compute height and check balance in O(n) time, do a single bottom-up traversal that returns both height and balanced flag for each node. A naive approach separately computing height for each node leads to O(n^2) in worst case (skewed tree) because height is recomputed repeatedly.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def height_and_balanced(root):
    """
    Returns (height, is_balanced)
    Height of empty tree = 0.
    """
    def dfs(node):
        if not node:
            return 0, True
        lh, lb = dfs(node.left)
        rh, rb = dfs(node.right)
        h = 1 + max(lh, rh)
        balanced = lb and rb and abs(lh - rh) <= 1
        return h, balanced
    return dfs(root)

Why naive is O(n^2): if you compute height(node) by recursing into children and call that at every node separately, skewed trees cause repeated O(n) work per node -> quadratic.

SRE monitoring note: running balance checks frequently on very large trees can add CPU and latency. Mitigations: run checks asynchronously at low priority, sample trees, cache previous results with incremental updates, or rate-limit checks. For in-process checks keep them O(n) and avoid blocking critical paths—profile and schedule during maintenance windows.

To perform inorder traversal (left, root, right) we can use recursion (straightforward) or an explicit stack to simulate recursion (iterative). Both return a list of node values. Handle empty root by returning [].

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

def inorder_recursive(root):
    """Recursive inorder traversal returning list of values."""
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)
    dfs(root)
    return result

def inorder_iterative(root):
    """Iterative inorder traversal using explicit stack."""
    result = []
    stack = []
    current = root
    # Go as left as possible, process node, then go right
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

Key points:

• Recursive uses call stack; iterative maintains explicit stack and is preferred when tree depth may cause recursion limits.
• For input [4,2,5,1,3] both return [1,2,3,4,5].

Complexity:

• Time: O(n) — visit each node once.
• Space: O(h) where h is tree height. Recursive uses O(h) call stack; iterative uses O(h) explicit stack. Worst-case skewed tree: O(n). Edge cases: root is None returns [].