Trees and Binary Search Trees Questions

We can do a single post-order DFS that returns the subtree height when balanced, or -1 as a sentinel if any subtree is unbalanced. That avoids recomputing heights and yields O(n) time.

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

def isBalanced(root):
    """
    Returns True if tree is height-balanced (|height(left)-height(right)| <= 1 for every node).
    Uses helper that returns height or -1 on imbalance. O(n) time, O(h) recursion space.
    """
    def height_or_minus_one(node):
        if not node:
            return 0
        lh = height_or_minus_one(node.left)
        if lh == -1:
            return -1
        rh = height_or_minus_one(node.right)
        if rh == -1:
            return -1
        if abs(lh - rh) > 1:
            return -1
        return 1 + max(lh, rh)

    return height_or_minus_one(root) != -1

Key points:

• Post-order ensures child heights known before parent decision.
• Sentinel (-1) short-circuits upward once imbalance found.

Time complexity: O(n) because each node visited once.
Space complexity: O(h) recursion stack (h = tree height), worst-case O(n) for skewed tree.

Proof sketch:

• Invariants: helper returns correct height if subtree balanced; returns -1 if any node in subtree violates balance.
• Base: empty node -> height 0 (balanced).
• Induction: assume children return correct value. If either child returned -1, propagate -1. Otherwise compare heights; if difference ≤1 return 1+max, else return -1. Therefore by induction all nodes produce correct output; final != -1 iff whole tree balanced.

Edge cases:

• Empty tree -> balanced.
• Single-node -> balanced.
• Large skewed tree -> detects imbalance and stops further work early.

Approach:

1. Do an inorder traversal to collect node values into a sorted list.
2. Rebuild a height-balanced BST by recursively choosing the middle element as root (divide-and-conquer).

Code implementation (Java):

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v){ val = v; }
}

public class Solution {
    public TreeNode balanceBST(TreeNode root) {
        List<Integer> vals = new ArrayList<>();
        inorder(root, vals);
        return build(vals, 0, vals.size() - 1);
    }
    
    private void inorder(TreeNode node, List<Integer> vals) {
        if (node == null) return;
        inorder(node.left, vals);
        vals.add(node.val);
        inorder(node.right, vals);
    }
    
    private TreeNode build(List<Integer> vals, int l, int r) {
        if (l > r) return null;
        int m = l + (r - l) / 2;
        TreeNode node = new TreeNode(vals.get(m));
        node.left = build(vals, l, m - 1);
        node.right = build(vals, m + 1, r);
        return node;
    }
}

Key concepts:

• Inorder of BST yields sorted sequence. Choosing middle element produces minimal-height tree (balanced).

Time & space complexity:

• Time: O(n) to traverse + O(n) to build = O(n).
• Space: O(n) for the list + recursion stack O(log n) expected for balanced build → overall O(n).

Edge cases:

• Empty tree (null), single node, duplicate values (keeps relative values; duplicates allowed).
• If original nodes themselves must be reused rather than creating new nodes, one can store node references instead of values and relink; complexity remains O(n).

Contrast with incremental rotation-based rebalancing (AVL/Red-Black):

• Rebuild approach: batch operation, simple to implement, O(n) time to fully balance once. Best when you can afford a full rebuild or when tree is highly unbalanced and rebalancing incrementally would be costly.
• AVL/Red-Black: maintain balance incrementally on each insert/delete with O(log n) time per operation (rotations and recoloring), no global O(n) rebuild needed. They provide continuous balance guarantees for dynamic workloads.
• Trade-offs: rebuild is optimal for offline/bulk rebalancing or occasional maintenance; AVL/Red-Black are suitable for online workloads requiring consistent worst-case search/insert/delete bounds and lower per-operation overhead.

To check strict isomorphism (structure + values) and optional mirror isomorphism, we can use recursion: at each node compare values and recursively check left-right correspondence; for mirror-allowed, allow either direct match or swapped match.

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

def is_isomorphic(t1, t2):
    """
    Strict isomorphism: same structure and same node values.
    """
    if t1 is None and t2 is None:
        return True
    if t1 is None or t2 is None:
        return False
    if t1.val != t2.val:
        return False
    return is_isomorphic(t1.left, t2.left) and is_isomorphic(t1.right, t2.right)

def is_isomorphic_with_mirror(t1, t2):
    """
    Isomorphism allowing optional mirror at any node: children may be swapped.
    At each node, either:
      - left matches left and right matches right (no swap), OR
      - left matches right and right matches left (swap)
    """
    if t1 is None and t2 is None:
        return True
    if t1 is None or t2 is None:
        return False
    if t1.val != t2.val:
        return False
    no_swap = (is_isomorphic_with_mirror(t1.left, t2.left) and
               is_isomorphic_with_mirror(t1.right, t2.right))
    swap = (is_isomorphic_with_mirror(t1.left, t2.right) and
            is_isomorphic_with_mirror(t1.right, t2.left))
    return no_swap or swap

Key points:

• Base cases handle nulls and leaf nodes: two nulls -> True; one null -> False; leaf nodes compare values and both children None.
• Recursion explores corresponding subtrees; with mirror option we allow swapped recursion.

Time & space complexity:

• Strict isomorphism: visits each node pair once → Time O(min(n1,n2)), effectively O(n) if sizes similar. Space (call stack) O(h) where h is tree height (O(n) worst-case, O(log n) balanced).
• With mirror allowed: worst-case still visits each node combination but each node does up to two recursive branch pairs. In pathological trees this can create overlap but because subproblems are distinct by node identity, complexity remains O(n) time for typical trees; however, due to the OR of two recursive checks, worst-case exponential behavior can occur for highly symmetric trees if not memoized. To guarantee O(n) time, memoize pairs (t1 id, t2 id) -> bool; with memoization time O(n1 * n2) worst-case but practically O(n). Space with memoization O(n1*n2) worst-case for table plus O(h) stack.

Edge cases:

• Different root values
• One or both trees empty
• Skewed trees (height = n)
• Identical multi-structure symmetric trees where mirror choices create repeated work (use memoization to avoid exponential blow-up).

Requirements & constraints:

• Multi-core, many concurrent readers/writers, correctness (linearizability), tolerate high concurrency, reasonable memory overhead.

High-level strategies (trade-offs):

• Global coarse-grained lock:

  • Simple: single mutex around whole BST.
  • Pros: easy correctness, no deadlocks.
  • Cons: serializes all ops -> poor scalability under contention.

• Fine-grained node locks (lock coupling / hand-over-hand):

  • Each node has a mutex. Traversal locks parent then child, releases parent after acquiring child.
  • Pros: more concurrency; readers/writers only block nearby ops.
  • Cons: increased complexity, lock overhead; potential for deadlocks if acquisition order not strict (always child after parent avoids cycles).

• Optimistic concurrency (read-only traversal + validation / versioning):

  • Traverse without locking using version counters or read-copy; before commit, acquire minimal locks and validate that traversed path/version unchanged.
  • Pros: excellent for read-heavy workloads, low locking overhead.
  • Cons: retries under contention; careful validation required to ensure linearizability.

• Lock-free / wait-free:

  • Use atomic CAS on pointers and careful memory reclamation (hazard pointers, epoch GC).
  • Pros: best latency under contention; no blocking.
  • Cons: highest complexity, subtle bugs, complex deletion handling.

Deadlocks, contention, performance:

• Avoid deadlocks by acquiring locks in a global order (top-down) and using lock coupling so only parent→child order occurs. Hold minimal locks and release early to reduce contention.
• For reads-dominated workloads, optimistic approach reduces contention and improves throughput. For write-heavy, fine-grained locking or lock-free gives better scaling than global lock.
• Memory reclamation matters: with optimistic or lock-free, use hazard pointers or epoch-based GC to avoid use-after-free.

Chosen approach: Optimistic search with fine-grained lock for updates (hybrid)

• Rationale: good read performance, bounded lock scope for updates, simpler than full lock-free and safer for production.

Operations (outline):

Search(key):

1. Traverse from root without acquiring locks, reading child pointers and node versions (version++ on modifications).
2. Upon reaching candidate or null, re-read the parent/child versions to validate none changed during traversal.
3. If validation passes, return result. If not, retry.

Insert(key, value):

1. Optimistic traversal to find parent where key should be inserted; record parent and its version.
2. Acquire lock on parent (single node lock). Re-check parent version and child pointer to ensure no concurrent modification.
3. If still valid and key not present, link new node (set child pointer) and increment parent version.
4. Release lock.

Delete(key):

1. Optimistic traversal to locate node and its parent; record versions.
2. Acquire locks in order: parent then node (to avoid deadlock).
3. Validate versions/pointers still match.
4. If valid, perform deletion:
   • If node has <=1 child: update parent's pointer to node's child.
   • If node has two children: either use in-order successor swap (lock successor path) or mark node logically deleted then physically remove later.
5. Update versions, release locks, and reclaim memory safely via epoch or hazard pointers.

Key points / best practices:

• Keep critical sections tiny; prefer logical deletion + asynchronous physical removal to simplify concurrency.
• Use versioned validation to avoid unnecessary locking on reads.
• Test with stress tests and formalize invariants; prefer well-known libraries/algorithms (e.g., Ellen’s lock-free BST or optimistic locking patterns) for production-critical systems.

Approach (brief)

• Use preorder with a null marker (e.g., "#") and a delimiter (e.g., ",").
• Serialize as a stream of tokens to a file/socket in chunks so we never hold whole output in memory.
• Deserialize by streaming tokens from that source and rebuilding the tree with an iterative stack-based algorithm to avoid recursion depth issues for very deep trees.

Streaming serialize/deserialze code (Python)

# Serialize: emit tokens to a writable binary/text stream in chunks
def serialize_stream(root, write_fn, null_marker="#", sep=",", buf_size=1<<20):
    buf = []
    def emit(token):
        buf.append(token)
        if sum(len(x) for x in buf) >= buf_size:
            write_fn(sep.join(buf))
            buf.clear()
    # iterative preorder to avoid recursion
    stack = [root]
    while stack:
        node = stack.pop()
        if node is None:
            emit(null_marker)
        else:
            emit(str(node.val))
            # push right then left so left processed first
            stack.append(node.right)
            stack.append(node.left)
    if buf:
        write_fn(sep.join(buf))

# Deserialize: read tokens from a readable stream lazily and build tree with a stack
def token_generator(read_fn, null_marker="#", sep=",", chunk_size=1<<20):
    rem = ""
    while True:
        chunk = read_fn(chunk_size)
        if not chunk:
            break
        s = rem + chunk
        parts = s.split(sep)
        rem = parts.pop()  # last may be incomplete
        for p in parts:
            yield p
    if rem:
        yield rem

def deserialize_stream(read_fn, null_marker="#", sep=","):
    tokens = token_generator(read_fn, null_marker, sep)
    # Build tree iteratively. Each frame: (node, state)
    try:
        first = next(tokens)
    except StopIteration:
        return None
    if first == null_marker:
        return None
    root = TreeNode(int(first))
    stack = [(root, 0)]  # state 0 = expecting left, 1 = expecting right
    for tok in tokens:
        while stack and stack[-1][1] == 2:
            stack.pop()
        if not stack:
            # extra tokens -> error
            raise ValueError("Extra data")
        parent, state = stack.pop()
        if tok == null_marker:
            # set child to None
            if state == 0:
                parent.left = None
                stack.append((parent, 1))
            else:
                parent.right = None
                stack.append((parent, 2))
        else:
            node = TreeNode(int(tok))
            if state == 0:
                parent.left = node
                stack.append((parent, 1))
            else:
                parent.right = node
                stack.append((parent, 2))
            # newly created node expects left next
            stack.append((node, 0))
    # final validation: all stack frames should be complete or nullable
    return root

Key concepts and reasoning

• Iterative traversal avoids recursion limits and big call stacks for 10M nodes.
• Streaming write_fn/read_fn are thin wrappers over file/socket write/read; we buffer tokens to amortize syscalls.
• Token generator handles chunk boundaries (rem variable) so tokens spanning chunks are reconstructed.
• Deserialization uses an explicit stack sized by tree height, not number of nodes — memory O(h) peak (h = tree height). For balanced 10M-node tree, h ~ 24, for worst-case skewed tree h ~ 10M (cannot avoid storing references to nodes if tree is that deep; consider balanced storage or different layout).

Complexity

• Time: O(n) to serialize and deserialize.
• Peak memory serialize: O(buf_size) + O(tree height) for iterative stack.
• Peak memory deserialize: O(tree height) + O(token buffer) (small), not O(n).

Trade-offs

• Compactness: using text tokens with delimiters is simple but larger than a binary packed format. Binary protocols (varint + single-byte null) reduce bytes but complicate streaming framing and human debugging.
• Streaming ability: delimiter-token streaming is friendly to chunked IO. Binary must define framing; both can stream.
• Error recovery: with simple token streams, a corrupted chunk may desync delimiters; add framing (length-prefixed blocks), checksums (per-chunk CRC), or record numbers to detect/skip corrupted blocks. Consider sequence numbers + checkpointing to resume deserialization mid-stream.
• Performance vs robustness: smaller separators and binary encoding = fewer bytes and faster IO but less tolerant to bit flips; text + separators easier to validate and repair.

Practical notes

• For very skewed trees (height ~ n), peak memory is inevitably O(n) to hold node references during reconstruction. If that’s unacceptable, consider external-memory representations (write nodes with parent index, reconstruct lazily), or use transformations to balanced encodings (e.g., left-child/right-sibling) or store as flat arrays with indices.
• Add versioning header and per-chunk checksums to support forward/backward compatibility and error recovery.