Binary Trees and Binary Search Trees Questions

Focuses on tree data structures, specifically binary trees and binary search trees. Candidates should understand node relationships, common traversals including in order, pre order, post order, and level order, and be able to implement traversals both recursively and iteratively. Cover binary search tree properties and operations including search, insertion, deletion, validation of binary search tree property, and finding the lowest common ancestor. Include problems on tree paths, height and balance calculations, serialization and deserialization, checking and restoring balance at a high level, and use cases in system design. Emphasize complexity analysis, recursion versus iterative solutions using stacks or queues, and handling edge cases such as duplicate keys and degenerate trees.

HardTechnical

59 practiced

Design and implement delete(key) for a BST where duplicate keys are allowed and represented by a 'count' integer stored at each node. Deletion should decrement count if greater than 1 and remove the node only when count reaches zero. Provide Python pseudocode, explain how search and traversal must adapt to counts, and discuss maintaining subtree sizes for order-statistics.

Sample Answer

Approach (brief):- Each node stores key, count (duplicates), left, right, parent (optional), and subtree_size = total count of keys in that subtree.- delete(key) searches for the node; if found and count>1, decrement count and propagate subtree_size updates up; if count==1, remove node using standard BST deletion (replace with successor/predecessor) and update subtree_size along the path.

Python pseudocode:

python

class Node:
    def __init__(self, key):
        self.key = key
        self.count = 1
        self.left = None
        self.right = None
        self.parent = None
        self.subtree_size = 1  # total counts in subtree including this node

def update_size(node):
    if not node: return 0
    left = node.left.subtree_size if node.left else 0
    right = node.right.subtree_size if node.right else 0
    node.subtree_size = left + right + node.count
    return node.subtree_size

def find(root, key):
    cur = root
    while cur:
        if key == cur.key: return cur
        cur = cur.left if key < cur.key else cur.right
    return None

def tree_min(node):
    while node.left: node = node.left
    return node

def transplant(root, u, v):
    # replaces subtree u with v; returns potentially new root
    if not u.parent:
        root = v
    elif u == u.parent.left:
        u.parent.left = v
    else:
        u.parent.right = v
    if v: v.parent = u.parent
    return root

def delete(root, key):
    node = find(root, key)
    if not node:
        return root  # key not found
    # Case 1: decrement count only
    if node.count > 1:
        node.count -= 1
        # propagate size fixes up
        p = node
        while p:
            update_size(p)
            p = p.parent
        return root
    # Case 2: physically remove node (count == 1)
    if not node.left:
        root = transplant(root, node, node.right)
        p = node.parent
    elif not node.right:
        root = transplant(root, node, node.left)
        p = node.parent
    else:
        succ = tree_min(node.right)
        # succ is successor; its subtree will replace node
        if succ.parent != node:
            root = transplant(root, succ, succ.right)
            succ.right = node.right
            succ.right.parent = succ
        root = transplant(root, node, succ)
        succ.left = node.left
        succ.left.parent = succ
        update_size(succ)  # recompute succ size after reattach
        p = succ.parent
    # update sizes up the tree
    while p:
        update_size(p)
        p = p.parent
    return root

Key concepts:- subtree_size counts duplicates: subtree_size = left.subtree_size + right.subtree_size + count.- Search: same as usual BST; when found, count tells how many duplicates exist at that key.- Traversal: inorder should output key repeated count times or return (key, count) pairs. For order-statistics (select/kth), use subtree_size to decide whether kth lies in left, current node (if k <= left_size + count and > left_size), or right (adjust k by left_size + count).

Time & space complexity:- Search/delete average O(h) where h = tree height; with balanced BST h = O(log n), worst-case O(n).- Space O(1) extra (in-place), recursion/parent updates depending on implementation.

Edge cases:- Deleting non-existent key.- Removing root node.- Successor has its own count (but successor.key != node.key since duplicates are stored in count; successor.count can be >1 — when replacing node with successor, transfer successor.count and adjust counts properly: in implementation above we moved nodes, so ensure successor.count is kept and node's count was 1).- Maintain parent pointers consistently.

Order-statistics note:- select(k): at node, left_size = node.left.subtree_size; if k <= left_size return select(left,k); elif k <= left_size + node.count return node.key; else return select(right, k - left_size - node.count).- rank(key): sum sizes left of path plus counts on equal node handling.

Trade-offs/alternatives:- Store duplicates as a linked list of occurrences instead of count — heavier memory, simpler removal of one occurrence.- Use balanced BST (AVL/Red-Black) to guarantee O(log n); must update subtree_size on rotations.

MediumTechnical

62 practiced

Implement level-order traversal that returns nodes grouped by level and also computes the maximum width (largest number of nodes at any level). Write Python function level_order_with_width(root) that returns (levels, max_width). Discuss memory versus CPU trade-offs for extremely wide levels and strategies to handle very large output.

Sample Answer

To perform a level-order traversal and compute the maximum width, we use BFS with a queue. We collect nodes per level (as values) and track the largest length seen. For extremely wide levels we discuss memory/CPU trade-offs and strategies (streaming, pagination, summarization, writing to disk, or sampling).

python

from collections import deque
from typing import Tuple, 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 level_order_with_width(root: Optional[TreeNode]) -> Tuple[List[List[int]], int]:
    """
    Returns (levels, max_width) where levels is a list of lists of node values per level,
    and max_width is the maximum number of nodes at any level.
    Time: O(n), Space: O(n) in worst case (for storing levels).
    """
    if not root:
        return [], 0

    q = deque([root])
    levels = []
    max_width = 0

    while q:
        level_size = len(q)
        max_width = max(max_width, level_size)
        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)
        levels.append(level_vals)

    return levels, max_width

Key points:- BFS guarantees correct grouping by level.- Time complexity O(n) where n = number of nodes.- Space complexity O(n) worst-case (one level may contain O(n) nodes for a shallow, wide tree).

Handling extremely wide levels / huge output:- Stream results instead of materializing: yield level lists via a generator to downstream consumers.- Pagination or chunking: emit or persist levels in chunks to disk/cloud storage (S3) to avoid O(n) memory.- Summarize or sample: if full list unnecessary, compute aggregates (counts, hashes) or use reservoir sampling to keep a bounded representative subset.- Parallel processing: if node processing is costly, process children in parallel but manage backpressure.- Trade-offs: streaming reduces peak memory but may increase latency or IO. Materializing enables random access but at high memory cost. Choose based on consumer needs (real-time vs batch).

HardTechnical

79 practiced

Two nodes of a BST were swapped by mistake. Design and implement an algorithm in Python to recover the BST by swapping them back without changing the tree structure. Aim for O(n) time and O(h) space (or O(1) if using Morris traversal). Explain how to detect swapped nodes by scanning the inorder sequence and give code sketch for fixing them.

Sample Answer

To recover a BST where two nodes were swapped, use the fact that an inorder traversal of a BST yields a sorted sequence. Scanning inorder, any out-of-order pairs indicate swapped nodes. There are two cases:- The two swapped nodes are non-adjacent in inorder: you see two inversions; first wrong = first node of first inversion, second wrong = second node of second inversion.- They are adjacent: you see one inversion; first wrong = first node, second wrong = second node.

Approach: perform an inorder traversal (recursive or iterative) tracking the previous node. Record the two nodes to swap, then swap their values. For O(1) extra space use Morris traversal; below is a clean recursive/iterative O(h) space implementation and a Morris variant sketch.

Python (iterative using stack, O(n) time, O(h) space):

python

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def recoverTree(root):
    """
    Recover BST by finding two swapped nodes during inorder scan and swapping their values.
    Time: O(n), Space: O(h) due to stack.
    """
    stack = []
    node = root
    prev = None
    first = second = None

    # Inorder iterative
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()

        # detect inversion: prev.val > node.val
        if prev and prev.val > node.val:
            if first is None:
                first = prev         # first time we see inversion
            second = node           # last node of inversion (updates if second inversion found)

        prev = node
        node = node.right

    # swap values of the two nodes found
    if first and second:
        first.val, second.val = second.val, first.val

Morris traversal variant (O(1) space): perform Morris inorder and apply the same inversion detection logic—replace the stack traversal by creating/tearing down threaded links (predecessor.right = current). The inversion detection and swap logic remain identical.

Key points:- We only swap node values, not structure.- Handles adjacent and non-adjacent swaps.- Time O(n). Space O(h) with stack or O(1) with Morris.Edge cases: tree with fewer than 2 nodes (no-op), duplicates allowed (algorithm relies on ordering; duplicates may still work if original BST allowed equal values consistently).

HardSystem Design

62 practiced

Design a concurrent in-memory BST that supports concurrent search, insert, and delete. Compare lock-based (coarse-grained and fine-grained) and lock-free approaches in terms of implementation complexity, throughput, and consistency guarantees. Discuss how such choices affect an AI model parameter server that sees millions of reads per second and moderate writes.

Sample Answer

Requirements & constraints:- In-memory BST supporting concurrent search/insert/delete.- High read throughput (millions/sec), moderate writes.- Strong consistency needed for model parameters (reads should see reasonably fresh values; some staleness may be acceptable if bounded).

High-level options & trade-offs1) Coarse-grained lock (single global mutex)- Implementation: trivial.- Complexity: very low.- Throughput: poor under high concurrency; reads and writes serialize.- Consistency: simple linearizability while lock held.- When appropriate: tiny scale or prototyping only.

2) Fine-grained locks (hand-over-hand / lock-coupling, per-node locks)- Implementation: moderate complexity. Must design lock acquisition order, avoid deadlocks.- Throughput: much better than coarse lock; reads can proceed concurrently on disjoint paths. But contended regions (root, hot keys) still bottlenecks.- Consistency: can provide linearizability if operations lock necessary nodes correctly.- Pitfalls: complexity increases for delete (rebalancing) and ensuring invariants while holding minimal locks.

3) Optimistic concurrency (versioned nodes, validate after traversal)- Implementation: moderate. Readers traverse without locks, validate node versions; writers update with locks or CAS.- Throughput: good for read-heavy workloads; readers rarely blocked.- Consistency: can provide linearizability with proper validation; retries required on conflicts.- Good compromise when reads dominate.

4) Lock-free / non-blocking (Harris-Michael style, CAS-based)- Implementation: high complexity. Requires careful pointer/tagging, ABA protection, memory reclamation (hazard pointers/epoch GC).- Throughput: excellent under high concurrency; progress guarantees (lock-free or wait-free variants) avoid priority inversion and deadlocks.- Consistency: can provide linearizability; correctness proofs or well-tested algorithms needed.- Operational costs: subtle bugs, hard to maintain, and slower single-operation latency due to CAS retries.

Crucial engineering concerns (applies to lock-free and optimistic):- Memory reclamation: must prevent use-after-free (hazard pointers, epoch-based reclamation).- ABA problem: pointer-tagging or hazard schemes.- Rebalance: self-balancing BSTs (AVL/Red-Black) add more complexity—consider using concurrent skip lists or B-trees instead.- Testing & tooling: stress testing, linearizability checkers.

Specific for AI model parameter server (millions reads/sec, moderate writes)- Read-optimized strategies: - Sharding: partition parameters across multiple BST instances to reduce contention. - Use read-copy-update (RCU) / copy-on-write for updates: readers access immutable snapshots without locks; writers create new versions for modified keys and publish atomically. Great for read-heavy workloads and low-latency reads. - Optimistic reads with validation: low overhead for readers; writers lock during updates. - Consider alternative data structures: concurrent skip lists or lock-free hash tables give comparable semantics with simpler implementations and better cache behavior.- Consistency choice: - For training, slightly stale reads (eventual or bounded staleness) are often acceptable—enables more aggressive optimizations (e.g., asynchronous updates). - For critical parameter reads (checkpointing, validation), provide strong consistency paths.

Recommendation- For an ML parameter server with millions of reads and moderate writes: avoid global locks. Prefer a read-optimized design: sharded data + RCU/immutable snapshots or optimistic reads with per-shard locking. If absolute minimal latency and high scalability are required and you have expertise, implement lock-free per-shard structures with epoch-based reclamation; otherwise, use optimistic locking or RCU which yield most read throughput with much lower implementation risk. Consider replacing BST with concurrent skip-list or sharded hash map for simpler, cache-friendly behavior.

HardTechnical

46 practiced

Implement an algorithm to find the maximum path sum in a binary tree where a path may start and end at any nodes (not necessarily root-to-leaf). Return both the maximum sum and the nodes along that path. Provide a Python implementation approach, explain why the naive O(n^2) approach can be improved to O(n), and handle cases with all negative values.

Sample Answer

Approach (brief): Do a single post-order DFS that at each node computes the maximum downward path sum starting at that node (can be just the node, node+left_down, or node+right_down) plus the node-to-node best passing through this node (node alone, node+left_down, node+right_down, node+left_down+right_down). Track global best sum and the node sequence for that best. This is O(n) because each node is visited once and constant work is done per node. The naive O(n^2) approach recomputes path sums for overlapping subtrees repeatedly; memoizing via a single DFS removes that.

Python implementation:

python

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

def max_path_sum_with_nodes(root):
    # global best: (sum, path_nodes_list)
    best = {"sum": float("-inf"), "nodes": []}

    def dfs(node):
        if not node:
            return (float("-inf"), [])  # no downward path from null

        # compute for children
        l_sum, l_path = dfs(node.left)
        r_sum, r_path = dfs(node.right)

        # convert negative-downs into "ignore child" by treating as 0-length path
        # but when all values are negative we must allow single node; handle with comparisons
        l_down = l_sum if l_sum > 0 else float("-inf")
        r_down = r_sum if r_sum > 0 else float("-inf")

        # possible downward paths starting at node:
        # 1) node alone
        down_options = [(node.val, [node.val])]
        if l_down != float("-inf"):
            down_options.append((node.val + l_down, l_path + [node.val]))
        if r_down != float("-inf"):
            down_options.append((node.val + r_down, [node.val] + r_path))

        # select best downward path (largest sum). If all children negative, node alone chosen.
        down_sum, down_nodes = max(down_options, key=lambda x: x[0])

        # possible best passing through node uses combinations:
        candidates = []
        candidates.append((node.val, [node.val]))
        if l_down != float("-inf"):
            candidates.append((node.val + l_down, l_path + [node.val]))
        if r_down != float("-inf"):
            candidates.append((node.val + r_down, [node.val] + r_path))
        if l_down != float("-inf") and r_down != float("-inf"):
            # join left -> node -> right: left path ends at node, right path starts at node
            candidates.append((node.val + l_down + r_down, l_path + [node.val] + r_path))

        # update global best
        for s, nodes in candidates:
            if s > best["sum"]:
                best["sum"] = s
                best["nodes"] = nodes

        return down_sum, down_nodes

    dfs(root)
    return best["sum"], best["nodes"]

Key points and reasoning:- The DFS returns the best downward-sum and its node sequence so reconstruction is immediate; when combining left+node+right we concatenate left path + [node] + right path.- To handle all-negative trees we allow "node alone" as a candidate; using >0 gating for child contributions ensures we don't force negative children to reduce sums but still permit single-node negatives to be chosen.- Time complexity: O(n) — each node processed once, constant-time merges.- Space complexity: O(h) recursion stack + O(k) for returned node lists where k is path length (<= n); overall O(n) worst-case for skewed tree.- Edge cases: null root (return -inf or define as 0 per requirement), single-node tree, duplicate values, long skewed trees.

Unlock Full Question Bank

Get access to hundreds of Binary Trees and Binary Search Trees interview questions and detailed answers.

Join thousands of developers preparing for their dream job.