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.

MediumTechnical

45 practiced

Implement serialize(root) and deserialize(data) for a Binary Search Tree using preorder traversal with explicit null markers in Python. The serialization should be compact and deserialization must reconstruct the exact original tree. Discuss complexity and alternatives optimized for BSTs.

Sample Answer

To serialize a BST with explicit null markers using preorder, output node values and a marker (e.g., "N") for null children. Deserialization reads tokens in order and rebuilds the exact tree recursively. Complexity: O(n) time, O(n) space. For BST-specific optimization you can omit null markers and reconstruct from preorder using value bounds (more compact).

Approach:1. Serialize: preorder traversal, append "N" for None, join with commas.2. Deserialize: consume tokens with an index/iterator and reconstruct nodes when token != "N".

Code:

python

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

def serialize(root):
    """Preorder with explicit null markers."""
    parts = []
    def dfs(node):
        if node is None:
            parts.append("N")
            return
        parts.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return ",".join(parts)

def deserialize(data):
    """Reconstruct exact tree from preorder with null markers."""
    tokens = data.split(",")
    it = iter(tokens)
    def build():
        val = next(it)
        if val == "N":
            return None
        node = TreeNode(int(val))
        node.left = build()
        node.right = build()
        return node
    return build()

Key points:- Time: O(n) visiting each node once.- Space: O(n) for output string and recursion stack (O(h) stack).- Edge cases: empty tree (data = "N"), negative/large values (string conversion handles), malformed input (would raise StopIteration).

BST-optimized alternative:- Omit null markers and serialize just preorder values. Reconstruct using bounds: use index pointer and allowed min/max to place nodes. This yields a more compact representation (no nulls) and still O(n) time; but that method relies on BST ordering (not safe for arbitrary binary trees).

HardTechnical

47 practiced

Two nodes of a BST are swapped by mistake. Implement a function to recover the tree without changing its structure. Aim for O(n) time and O(1) extra space (Morris traversal) or O(h) with a stack. Provide a Python implementation or detailed algorithm and explain edge cases.

Sample Answer

To recover a BST where two nodes are swapped, perform an inorder traversal to find the two misplaced nodes (because inorder of BST is sorted). Using Morris traversal gives O(n) time and O(1) extra space. We detect two nodes: first when a previous node > current (first = prev, second = current); if another inversion occurs, update second = current. After traversal swap their values.

python

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

def recoverTree(root):
    """
    Recover BST by Morris inorder traversal: O(n) time, O(1) extra space.
    """
    first = second = prev = None
    node = root

    while node:
        if node.left is None:
            # visit node
            if prev and prev.val > node.val:
                if first is None:
                    first = prev
                second = node
            prev = node
            node = node.right
        else:
            # find predecessor
            pred = node.left
            while pred.right and pred.right is not node:
                pred = pred.right
            if pred.right is None:
                pred.right = node  # make thread
                node = node.left
            else:
                pred.right = None  # remove thread, visit node
                if prev and prev.val > node.val:
                    if first is None:
                        first = prev
                    second = node
                prev = node
                node = node.right

    if first and second:
        first.val, second.val = second.val, first.val

Key points:- Handles adjacent and non-adjacent swaps: first is set at first inversion; second updated at each inversion.- Time: O(n). Space: O(1) extra (threads modify tree temporarily).Edge cases:- Empty tree or single node: nothing to do.- Adjacent swapped nodes (one inversion) or separated swapped nodes (two inversions).- Large/deep trees: Morris avoids recursion/stack depth.

EasyTechnical

58 practiced

Explain the difference between a binary tree and a binary search tree (BST). Include node relationship rules, the BST ordering invariant, typical use-cases where a BST is preferred, and common strategies for handling duplicate keys in practice.

EasyTechnical

84 practiced

Implement functions to find the minimum and maximum values in a BST iteratively. Use Java or C++. Explain why these operations run in O(h) time and show behavior on degenerate (pathological) BSTs.

Sample Answer

To find min/max in a BST iteratively, follow the invariant: min = leftmost node, max = rightmost node. Both iterate down one child each step, so runtime is O(h) where h is tree height.

java

// Java implementation
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

public class BSTUtils {
    // Iterative min: returns null if tree empty
    public static TreeNode findMin(TreeNode root) {
        if (root == null) return null;
        TreeNode cur = root;
        while (cur.left != null) cur = cur.left;
        return cur;
    }

    // Iterative max: returns null if tree empty
    public static TreeNode findMax(TreeNode root) {
        if (root == null) return null;
        TreeNode cur = root;
        while (cur.right != null) cur = cur.right;
        return cur;
    }
}

Key points:- Time complexity: O(h). Each loop moves one level down following left (for min) or right (for max) pointers only.- Space complexity: O(1) iterative (no recursion).- Degenerate (pathological) BSTs: If the BST is a linked list (all nodes only left or only right), h = n, so operations become O(n). Balanced BSTs have h = O(log n), so operations are O(log n).- Edge cases: root == null (return null), single-node tree (returns root).

HardSystem Design

52 practiced

You're designing a serialization format for millions of binary trees to store and transmit in a distributed system. Compare JSON-like with null markers, compact binary formats, and delta compression between similar trees. Discuss space/time trade-offs, parsing cost, backward compatibility, and recommend an approach for production.

Sample Answer

Requirements:- Store/transmit millions of binary trees (node payloads binary/opaque), optimize for storage and network.- Fast serialization/deserialization (low CPU), support streaming, partial reads, schema evolution/backward compatibility, and optional dedup/delta for similar trees.- Operate in distributed deployment: multiple languages, rolling upgrades.

High-level comparison

1) JSON-like with null markers- Format: text, e.g. {"v":1,"left":{...},"right":null} or bracketed lists with explicit nulls.- Space/time: largest on-wire size due to text and field names; slowest parse (string→binary); good compressibility with gzip but less efficient than binary.- Parsing cost: high CPU and memory, higher GC pressure in high throughput services.- Backward compatibility: excellent — extra/missing fields tolerated, easy to version.- Pros: human-readable, easy debug, cross-language.- Cons: poor network/storage efficiency at scale.

2) Compact binary format- Format: protobuf/flatbuffers/CBOR/custom binary: e.g., pre-order with bitmask for child presence + length-prefixed payloads.- Space/time: much smaller; no field names; lower CPU for parsing if using zero-copy (flatbuffers) or simple iterative decode.- Parsing cost: low to medium depending on chosen library; flatbuffers allows zero-copy reads, protobuf needs parsing but fast.- Backward compatibility: protoc-based schemas support optional/unknown fields; careful schema design required.- Pros: best general trade-off for speed and size, fits production needs.- Cons: more complex to evolve if payloads change; not human readable.

3) Delta compression between similar trees- Format: store a base tree + edits (diffs) as operations (insert/delete/modify pointers/payloads) or use semantic transforms; or use sequence-level compression (rsync-like).- Space/time: can yield large savings when trees are similar (e.g., ASTs, snapshots). Computing deltas is CPU intensive and may need heuristics (tree edit distance approximations). Applying deltas adds deserialization complexity and latency.- Parsing cost: higher: must reconstruct base + apply patch. If bases are remote or evicted, complexity increases.- Backward compatibility: trickier — diffs must remain interpretable as schemas evolve and require consistent base selection/versioning.- Pros: great for storage and bandwidth when similarity high.- Cons: operational complexity, cache management, harder to stream/partial-read.

Recommendation for productionUse a hybrid approach:- Primary storage/transit: compact binary format (protobuf or flatbuffers). Design node encoding as: [node-header byte bitmask for left/right presence][varint payload-length][payload bytes]. Use pre-order streaming so you can stream/encode/decode without whole-tree buffering.- Schema/versioning: include a small version tag and use optional fields; keep backward-compatible changes (add optional fields).- Compression: enable transport-level compression (zstd or snappy) to capture repetitive patterns cheaply; choose compression level tuned for latency.- Delta layer (optional): implement delta compression as an asynchronous optimization for archival or large-batch replication where trees are highly similar. Maintain base references, TTLs, and fall back to full tree when base unavailable. Compute deltas off the hot path (background jobs) or only for bulk transfers.- Operational considerations: provide tooling to inspect binary trees (debug dumps to JSON for devs), monitor decode latency, and run canary rollouts for schema changes.

Why this balances needs- Compact binary gives low latency and small size for high-throughput services.- Streaming-friendly pre-order + presence bitmask enables partial processing and zero-copy where possible.- Transport compression captures additional redundancy at low implementation cost.- Delta compression yields extra savings where justified but avoids adding runtime complexity to hot path.

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.