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

53 practiced

Given an unbalanced BST used in production that is causing latency spikes, propose algorithmic and operational mitigations: include immediate short-term fixes and long-term design changes (e.g., periodic rebalancing, background rebuilding, switching to balanced trees). Describe monitoring metrics you would add to detect reoccurrence.

Sample Answer

Situation: In production we discover an unbalanced BST (used by a feature index or in-request cache) causing tail-latency spikes and impacting model inference throughput.

Short-term (immediate, low-risk)- Throttle/limit: Add request-rate limiting or circuit breaker to protect downstream ML serving while we diagnose.- Fall-back path: Route a percentage of requests to a simpler, stable code path (e.g., linear scan or hashed lookup) to reduce worst-case latency.- Hot-node mitigation: Identify worst-case/degenerate keys (via logs) and cache those results in an LRU in-memory cache (Redis/local) to avoid repeated deep-traversals.- Operational rollback: If a recent change triggered imbalance, roll back that deploy.

Medium-term (weeks)- Background rebalancing: Implement an online rebalancer that performs rotations or rebuilds subtrees incrementally in background with rate-limiting to avoid CPU/IO spikes. Use copy-on-write or epoch-based swapping so reads remain lock-free.- Periodic maintenance window: Schedule low-traffic off-peak full rebuilds of the tree to a balanced form (AVL/Red-Black or perfectly balanced) with safe swapping.

Long-term (design)- Replace structure: Move from unbalanced BST to a balanced data structure (e.g., Red-Black tree, B-tree, skip list) or a hash-based index if ordering isn't required.- Use proven stores: Offload to a production-grade datastore (e.g., RocksDB, LevelDB, or managed KV) which handles compaction and balancing.- Sharding and partitioning: Split keyspace to reduce tree depth per shard; add consistent hashing to distribute load.

Monitoring & Alerts (to detect recurrence)- Latency p50/p95/p99 and p999 for operations touching the tree; alert on p99/p999 crossing thresholds or sudden increase.- Operation cost metrics: average tree depth visited per lookup, number of rotations/rebalances, and distribution of traversal lengths.- Error/retry rates and CPU utilization per service thread (spikes may indicate heavy tree operations).- Hot-key frequency and tail of access distribution (skew detection).- Background maintenance throughput and time to rebuild.- Changeset/deploy correlation: annotate metrics with deploy IDs to catch regressions.

Why this approach- Immediate mitigations protect user-facing SLAs while non-blocking background fixes reduce risk. Long-term replacement with balanced/managed systems removes algorithmic cause and scales reliably. Monitoring focuses on tail behavior and structural signals so recurrence is detected before SLA impact.

HardTechnical

44 practiced

You must design a thread-safe BST for concurrent reads and writes in an online feature store that supports low-latency lookups and frequent updates. Describe a fine-grained locking scheme or lock-free approach, discuss correctness, deadlock avoidance, and performance trade-offs. You do not need to provide full code but outline concurrency primitives and per-node metadata.

Sample Answer

Approach summary:I’d use a fine-grained locking BST based on hand-over-hand (lock coupling) with optimistic reads and version stamps; as an alternative I’ll describe a lock-free variant using CAS on child pointers (Chase-Lev style) and marking for logical deletion. Both aim for low-latency reads and frequent updates.

Fine-grained locking design (recommended for simplicity & correctness):- Per-node metadata: key, value, left/right pointers, mutex (std::mutex or pthread_mutex), version counter (uint64) and a bool deleted flag.- Read path: optimistic read — traverse without locks while reading version counters on entry/exit of node; if any node’s version changed, retry with lock-coupling. This makes common reads lock-free in the fast-path.- Write path (insert/delete/update): use lock coupling: acquire lock on parent, then child, release parent once child locked, proceed downwards. Before modifying a node, increment its version (write barrier) and set deleted flag for deletes. After structural change update version and release locks.Correctness & linearizability:- Version counters + write barriers ensure readers observe either pre- or post-update consistent state. Writers serialize structural changes via per-node locks so tree invariants (BST ordering and pointer consistency) are preserved.Deadlock avoidance:- Always acquire locks top-down and never hold locks while acquiring a higher-up lock. Use try-lock with backoff and restart if acquisition order would block -> prevents cycles.Performance trade-offs:- Pros: low contention when operations target different subtrees; optimistic reads minimize latency for lookups.- Cons: writes near root or skewed data cause contention; lock overhead for many small writes.Lock-free alternative (for extreme scale):- Per-node: atomic left/right pointers with mark/tag bits, version tag.- Use CAS to link/unlink nodes and a two-phase logical-deletion then physical-removal (helping) algorithm (similar to Harris et al. lock-free BST).- Pros: eliminates blocking, better throughput under high concurrency; Cons: much higher implementation complexity, ABA concerns (use hazard pointers or epoch GC), and harder to reason about correctness.Practical recommendation:- Start with fine-grained locking + optimistic reads. Profile hotspots; if writes dominate and latency suffers, consider a well-tested lock-free library or partition keys (sharding) to avoid single-tree contention.

MediumTechnical

55 practiced

Analyze the time and space complexity differences between recursive and iterative tree traversals (inorder) for balanced vs skewed trees. Include worst-case call stack depth, auxiliary data structure sizes, and the impact on languages like Python without tail-call elimination. Provide recommendations for production ML code.

HardTechnical

59 practiced

Design an algorithm to find the kth smallest element in a very large BST stored on disk where you only have limited memory (e.g., few MBs). Explain an approach that minimizes random disk seeks by streaming nodes sequentially and discuss worst-case IO and memory trade-offs. Optionally sketch code that uses iterators and external merging.

Sample Answer

Approach summary- We cannot load the whole BST; do an external in-order traversal that streams nodes sequentially from disk to minimize random seeks. If the tree is stored as pages (B-tree style) or as nodes in files, lay out nodes in depth-first order or maintain a contiguous on-disk in-order layout. Then perform a streamed in-order scan (sequential reads) and count until k. If the tree layout is arbitrary, first create a sequential iterator by scanning pages and producing sorted runs via external merge.

Algorithm options1) Best case (on-disk in-order layout): Single-pass streaming in-order traversal - Open file, stream nodes in in-order order (or pages mapped to in-order), count nodes; when count==k return value. - IO: O(#pages) sequential reads. Memory: O(1)–O(stack_page) (~few KB).

2) General case (arbitrary layout): External sort/merge of leaf-level keys - Phase A: Read disk in large sequential chunks (fit memory), perform in-memory traversal of contained nodes to extract key list, sort that chunk -> produce sorted runs written to disk. This uses only sequential reads/writes. - Phase B: K-way external merge of runs using a min-heap of size m (m = number of runs we can buffer), pop elements until kth seen. - IO: O(N/B * log_{M/B}(N/B)) worst-case where B=page size, M=memory size; dominated by sequential reads/writes. Memory: O(M) buffer, heap size = number of runs (bounded by M/B).

Why this minimizes random seeks- Both approaches do only sequential reads/writes and a small in-memory heap/stack. No random single-node fetches. External sorting and merging are well-known for optimizing disk IO.

Worst-case IO & trade-offs- If tree is arbitrarily scattered, worst-case requires reading all nodes and writing/reading sorted runs: ~2×N (write runs + read during merge) sequential page IOs per pass. More memory (M) reduces number of runs => fewer merge passes => lower IO. If M large enough to hold entire tree, single-pass in-memory sort: O(N) IO once. If layout already sorted in-order, you get O(N) one-pass read and constant memory.

Sketch: iterators + external merge (Python-like)

python

# stream_run() yields keys from a memory-sized scan of disk, sorted
def stream_runs(disk_reader, mem_limit):
    buffer=[]
    for node in disk_reader.stream_nodes():    # sequential
        buffer.append(node.key)
        if memory_usage(buffer) >= mem_limit:
            buffer.sort()
            yield buffer
            buffer=[]
    if buffer:
        buffer.sort()
        yield buffer

def kth_smallest_via_merge(disk_reader, mem_limit, k):
    import heapq
    runs = []  # file-backed runs from stream_runs; assume we can open iterators
    for run in stream_runs(disk_reader, mem_limit):
        runs.append(iter(run))
    heap=[]
    for i, it in enumerate(runs):
        try:
            v=next(it)
            heapq.heappush(heap,(v,i))
        except StopIteration: pass
    count=0
    while heap:
        v,i=heapq.heappop(heap)
        count+=1
        if count==k: return v
        try:
            nv=next(runs[i])
            heapq.heappush(heap,(nv,i))
        except StopIteration:
            pass
    raise IndexError("k out of range")

Edge cases & practical notes- If keys duplicate, count each occurrence per requirement. If tree nodes contain large payloads, only stream keys/pointers to reduce IO. Use OS read-ahead, large sequential reads, and memory-mapped IO where available. If latency matters, store a B-tree / clustered index to make range scans inherently sequential.

HardTechnical

52 practiced

Design a BST iterator that supports concurrent modifications: it should either iterate over a consistent snapshot as of iterator creation, or provide weakly consistent results without crashing. Describe the data structures (versioning, copy-on-write, optimistic validation) and the trade-offs between memory and latency. Provide pseudo-code for snapshot creation and iterate methods.

Sample Answer

Approach summary:- Offer two modes: strong (consistent snapshot) and weak (lock-free, best-effort). Use copy-on-write (COW) or structural versioning for snapshot; use optimistic validation for weak iterator to detect concurrent structural changes and either retry or skip nodes.

Data structures:- Each BST node: {key, value, left, right, version}. Mutations increment node's version and, under COW, create new nodes up the path.- Tree root is an atomic reference to current versioned root (pointer to immutable tree root for snapshots).- Snapshot: capture root pointer (immutable view). Strong snapshots = read-only traversal of captured root.- Weak iterator: in-order traversal of live tree; before yielding a node, validate node.version unchanged since visited pointer (optimistic).

Trade-offs:- Memory: strong snapshots (COW) increase memory: O(changed_nodes) per write; full copy = O(n). Weak iterator uses little extra memory.- Latency: writes slower with COW (must copy path O(h)). Strong reads fast and stable. Weak iteration has low creation cost but may retry and see inconsistent order/duplicates.

Pseudo-code (Python-like):

python

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

# snapshot creation (strong)
def create_snapshot(tree):
    # atomic read of root pointer
    root = atomic_load(tree.root)  
    return Snapshot(root)

class Snapshot:
    def __init__(self, root): self.root = root
    def iterate(self):
        # in-order stack traversal over immutable root
        stack, node = [], self.root
        while stack or node:
            while node:
                stack.append(node); node = node.left
            node = stack.pop()
            yield node.key, node.val
            node = node.right

# weak iterator (optimistic validation)
def weak_iter(tree):
    stack, node = [], atomic_load(tree.root)
    while stack or node:
        while node:
            stack.append((node, node.ver)); node = node.left
        node, ver = stack.pop()
        # optimistic check: ensure node still reachable and version unchanged
        if node.ver == ver:
            yield node.key, node.val
        # else skip or optionally restart subtree traversal
        node = node.right

Notes:- For strong snapshots, use path-copying on writes: when inserting/deleting, clone nodes on path and atomically swap root.- For production ML systems, prefer snapshots for stable reads during model serving (consistent feature indexing) despite extra memory; use weak iterators for background analytics where eventual consistency is acceptable.

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.