Linked Lists and Trees Questions

Dynamic and pointer based data structures including linked lists and tree structures commonly tested in interviews. For linked lists cover node based representation, traversal, insertion at head and tail, deletion, searching, reversing a list, detecting cycles, and tradeoffs versus array based lists. For trees cover basic concepts such as binary trees and binary search trees, tree node representation, insertion and deletion in search trees, recursion patterns, and traversal algorithms including depth first search with in order pre order and post order variants and breadth first search. Also include problem solving patterns such as recursion and iterative stack or queue based approaches, analysis of time and space complexity in plain terms, and common interview tasks such as lowest common ancestor, tree balancing awareness, and converting between representations. Practice includes implementing algorithms, writing traversal routines, and reasoning about correctness and performance.

EasyTechnical

71 practiced

Implement mergeTwoLists(l1, l2) that merges two sorted singly linked lists into one sorted list. Write in Python, Java, or C++ and ensure O(n1 + n2) time and O(1) extra space (excluding output). Example: l1=[1,3,5], l2=[2,4] → [1,2,3,4,5]. Discuss use of a dummy head and pointer manipulation.

Sample Answer

We can merge two sorted singly linked lists in O(n1 + n2) time and O(1) extra space by reusing nodes and manipulating next pointers. A dummy head simplifies pointer logic by avoiding special-casing the head of the result list.

Approach:- Create a dummy node and a tail pointer pointing at it.- While both lists non-empty, compare l1.val and l2.val, attach the smaller node to tail.next, advance that list and tail.- After loop attach remaining nodes from the non-empty list.- Return dummy.next.

Python implementation (in-place, constant extra space):

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    # Dummy head to simplify edge cases (empty result head)
    dummy = ListNode()
    tail = dummy

    # Merge by re-linking existing nodes (no new nodes allocated)
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    # Attach remaining nodes (one of l1 or l2 is None)
    tail.next = l1 if l1 else l2

    return dummy.next

Key points:- Dummy head removes special handling for the first node and makes code uniform.- We move existing nodes (tail.next = l1 or l2), so space is O(1) excluding output.- Time complexity O(n1 + n2); space O(1).Edge cases:- One or both inputs are None.- Lists with duplicate values.- Very different lengths (handled by attaching remainder).

HardTechnical

134 practiced

Some doubly linked lists include nodes with a child pointer pointing to another doubly linked list (multilevel). Implement flatten(head) that flattens the list depth-first into a single-level doubly linked list in-place. Provide both recursive and iterative approaches and discuss stack depth and in-place splicing of next/prev pointers.

Sample Answer

To flatten a multilevel doubly linked list depth-first in-place, we splice child lists between a node and its next, keeping prev/next pointers correct. Two common approaches: recursive DFS that returns tail, and iterative using an explicit stack to avoid recursion depth.

Recursive (returns tail to splice efficiently):

python

class Node:
    def __init__(self, val, prev=None, next=None, child=None):
        self.val = val; self.prev = prev; self.next = next; self.child = child

def flatten_recursive(head):
    if not head: return None

    def dfs(node):
        curr = node
        tail = node
        while curr:
            next_node = curr.next
            if curr.child:
                child_head = curr.child
                child_tail = dfs(child_head)           # recurse into child
                # splice child between curr and next_node
                curr.next = child_head
                child_head.prev = curr
                if next_node:
                    child_tail.next = next_node
                    next_node.prev = child_tail
                curr.child = None
                tail = child_tail
            else:
                tail = curr
            curr = next_node
        return tail

    dfs(head)
    return head

Iterative with stack (explicit control, avoids recursion depth limits):

python

def flatten_iterative(head):
    if not head: return None
    stack = []
    curr = head
    while curr:
        if curr.child:
            if curr.next:
                stack.append(curr.next)               # save continuation
            # splice child
            curr.next = curr.child
            curr.next.prev = curr
            curr.child = None
        if not curr.next and stack:
            nxt = stack.pop()
            curr.next = nxt
            nxt.prev = curr
        curr = curr.next
    return head

Key points and reasoning:- Both perform depth-first order: visit node, then its child subtree, then saved next pointers.- Splicing is done in-place: adjust curr.next, child_head.prev, child_tail.next, next.prev; set child to None to avoid cycles.- Time complexity O(n) where n = total nodes across levels; each node visited/linked constant times.- Space: recursive uses O(h) call stack where h is max nesting depth; iterative uses O(k) stack where k is number of saved next pointers (worst-case O(n) for many siblings). Iterative is preferred when recursion depth may overflow.- Edge cases: empty head, single node, child with its own children, many siblings, circular references in malformed input. Validate inputs if necessary.

HardTechnical

82 practiced

Implement kthSmallest(root, k) to find the k-th smallest element in a BST. Provide both iterative stack-based inorder and Morris traversal (O(1) space) approaches and discuss trade-offs. Mention augmenting nodes with subtree sizes for repeated queries to achieve O(log n) runtime per query.

Sample Answer

We can get the k-th smallest in a BST by doing an inorder traversal (sorted order). Below are two approaches: iterative stack-based inorder (O(h) extra space) and Morris traversal (O(1) space). I also describe augmenting nodes with subtree sizes for repeated queries (O(log n) per query).

Approach 1 — Iterative stack-based inorder:- Walk left pushing nodes until null.- Pop, decrement k; when k==0 return node.val.- Move to right child and repeat.

python

# Iterative stack-based inorder O(h) space, O(k) time
def kthSmallest_stack(root, k):
    stack = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right
    raise ValueError("k out of range")

Approach 2 — Morris traversal (O(1) extra space, modifies tree temporarily):- For each node, if left is None visit it and go right.- Else find predecessor (rightmost in left subtree). If predecessor.right is None, set it to current and go left. If predecessor.right is current, restore None, visit current, go right.- Count visits; return when count == k.

python

# Morris inorder traversal O(1) extra space, O(n) time
def kthSmallest_morris(root, k):
    count = 0
    cur = root
    while cur:
        if cur.left is None:
            count += 1
            if count == k:
                return cur.val
            cur = cur.right
        else:
            pred = cur.left
            while pred.right and pred.right is not cur:
                pred = pred.right
            if pred.right is None:
                pred.right = cur  # thread
                cur = cur.left
            else:
                pred.right = None  # remove thread
                count += 1
                if count == k:
                    return cur.val
                cur = cur.right
    raise ValueError("k out of range")

Key concepts and trade-offs:- Stack approach: simple, robust, supports recursion-like behavior, O(h) space where h is tree height. Good for single queries and easier to reason about.- Morris traversal: O(1) extra space and still O(n) time worst-case; it temporarily mutates tree pointers but restores them. Slightly more complex; not thread-safe and risky if traversal interrupted.- Both are O(k) time in average when k << n; worst-case O(n).

Augmenting nodes for repeated queries (order-statistics tree):- Store size at each node: size = 1 + size(left) + size(right).- To find k-th smallest: at node, let L = size(left). If k == L+1 return node; if k <= L go left; else go right with k -= L+1. Each step is O(1) so overall O(h) ≈ O(log n) for balanced BST.- Maintain sizes on insert/delete (update along path) so queries stay fast.

Edge cases:- k <= 0 or k > n -> error/exception.- Unbalanced trees: stack/morris still work but stack size could be O(n).- If tree structure can change concurrently, prefer stack approach or copy.

Complexities:- Stack approach: Time O(h + k) ~ O(k) worst-case O(n); Space O(h).- Morris: Time O(n) worst-case, Space O(1).- Augmented sizes: Query O(h) ~ O(log n) if balanced; update O(h) per insert/delete.

Choose based on constraints: use stack for simplicity, Morris when strict O(1) extra space is required, and augment sizes when many queries must be answered efficiently.

HardSystem Design

88 practiced

Beyond token-based string serialization, design a compact binary serialization for a binary tree optimizing for space (e.g., bit-level packing for null markers and varint encoding for integers). Describe an encoding scheme, a streaming parser, how you handle endianness and versioning, and trade-offs between compactness and CPU parsing cost.

Sample Answer

Requirements & constraints:- Compact binary format for arbitrary binary trees (nullable children, integer payloads), streaming-friendly, portable across architectures, versionable.- Optimize space: bit-level null markers, varint for integers, minimal headers.

Encoding scheme (high level):- File header (fixed): - 4 bytes magic "BTRE" (0x42 0x54 0x52 0x45) - 1 byte version (v1 = 0x01) - 1 byte flags (bit0 = endianness marker if needed; default little-endian semantics for multibyte integers—see below)- Body: preorder traversal (node, left subtree, right subtree) emitting per-node compact records: - 1 control byte: bitmap for children presence in low 2 bits (bit0 = hasLeft, bit1 = hasRight). Remaining 6 bits reserved for future. - payload: signed/unsigned integer encoded with unsigned LEB128 (varint). If payloads can be negative, use ZigZag then LEB128.- Nulls are implicit: when hasLeft==0 you skip left subtree entirely; same for right.

Space optimizations:- Control bytes are packed per node (2 bits used). For extreme compactness, group N control bits into a control-bitstream preceding a block of payloads — e.g., write control bits consecutively and flush by bytes; then write payloads in order. This reduces 7 unused bits per node but complicates streaming slightly.- Use ZigZag + LEB128 to make small absolute values 1 byte.

Streaming parser (incremental / single-pass):- Read header, validate magic/version.- Use a stack-driven preorder parser: - Read next control byte (or pop next 2 control bits from control-bitstream). - Read next varint -> node.value. - If hasRight then push a marker to process right later. - If hasLeft then continue (next bytes represent left subtree). - Else if stack has right markers, pop and continue to right.- Parser reads bytes sequentially; varint decode reads up to 10 bytes (64-bit). For control-bitstream variant, maintain a byte buffer and a bit cursor.

Endianness & portability:- Varint (LEB128) is endianness-independent (byte-wise). Use LEB128 for integers—no multi-byte fixed-endian ints.- Header flags indicate semantic choices (signedness, payload type). Default: ZigZag+LEB128 for signed integers; defines version so future formats can change.- For any fixed-width fields (counts, timestamps) include explicit endianness (specify little-endian) or prefer varints always.

Versioning & extensibility:- Version byte in header. New versions can add flags, optional sections, or change traversal order.- Use reserved bits in control byte or a TLV extension region after header for optional metadata.- Backward compatibility: v1 parser ignores unknown flags/extension blocks it can skip by reading a length field.

Trade-offs (compactness vs CPU parsing cost):- Compactness wins: control-bitstream (bit-packed control bits) + varints minimize size but requires bit-level ops and buffering — higher CPU & implementation complexity.- Simpler: per-node control byte is easier to parse (byte aligned) but wastes up to 7 bits/node.- LEB128 is compact for small ints, but decoding uses loops and branches (slower than fixed 4/8-byte integers). Fixed-width integers are faster but larger.- Streaming & preorder is very friendly to single-pass and low memory, but random access to subtrees requires building index or using BFS+index table (extra space).- Consider hybrid: block-based encoding (e.g., groups of 1024 nodes) where each block has a small header + packed control bits + payloads; enables faster skipping/seeking at block granularity.

Example encode flow (simplified):1. Write header: magic, version, flags.2. Preorder recursive emit(node): - write control byte (hasLeft|hasRight) - write ZigZagLEB128(node.value) - if hasLeft emit(left) - if hasRight emit(right)

Parser pseudocode outline:- read header- function parseStream(): - stack = [] - loop: - control = readControlByte() - value = readVarintZigZag() - emit node(value) - if control.hasRight push marker - if control.hasLeft continue - else while stack and not next right: pop; if found handle right

Final notes:- Choose control-bitstream when minimal bytes matter (networks, embedded). Choose per-node control byte for simpler, faster parsing.- Use tests: fuzz round-trip, measure bytes/CPU, and add a compatibility test matrix for versions.

MediumTechnical

90 practiced

Implement isBalanced(root) to check whether a binary tree is height-balanced (for every node, left and right heights differ by at most 1) in O(n) time. Avoid repeated height computations by using a helper that returns height or a sentinel for imbalance. Provide proof sketch for correctness.

Sample Answer

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.

python

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.

Unlock Full Question Bank

Get access to hundreds of Linked Lists and Trees interview questions and detailed answers.

Join thousands of developers preparing for their dream job.