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.

MediumTechnical

92 practiced

Given a singly linked list where each node has an extra 'random' pointer to any node or None, implement a Python function that returns a deep copy of the list. Aim for O(n) time and O(1) extra space (no hash map). Explain the three-step weaving/unweaving technique.

Sample Answer

Approach: use the three-step weaving technique — interleave cloned nodes with originals, set cloned random pointers by using original.random.next, then unweave to separate the cloned list. This achieves O(n) time and O(1) extra space (no hash map).

python

class Node:
    def __init__(self, val, nxt=None, random=None):
        self.val = val
        self.next = nxt
        self.random = random

def copy_random_list(head: Node) -> Node:
    if not head:
        return None

    # Step 1: Interleave cloned nodes after each original node
    cur = head
    while cur:
        clone = Node(cur.val)
        clone.next = cur.next
        cur.next = clone
        cur = clone.next

    # Step 2: Set random pointers for clones
    cur = head
    while cur:
        if cur.random:
            cur.next.random = cur.random.next
        cur = cur.next.next  # move to next original

    # Step 3: Unweave to restore original list and extract cloned list
    cur = head
    clone_head = head.next
    while cur:
        clone = cur.next
        cur.next = clone.next  # restore original next
        cur = cur.next
        if cur:
            clone.next = cur.next  # set clone's next
    return clone_head

Key points:- Interleaving lets you find a clone from an original in O(1): original.next.- Setting clone.random: original.random.next (if random exists).- Unweaving restores original list and builds cloned list without extra structures.

Complexity:- Time: O(n) — each pass is linear.- Space: O(1) extra (ignoring cloned nodes which are required).

Edge cases:- Empty list- Nodes with random = None- Random pointing to self or duplicates — handled correctly

Alternative: use a hash map original->clone for clarity (O(n) time, O(n) space) if O(1) space is not required.

EasyTechnical

94 practiced

Write a function kth_from_end(head, k) that returns the k-th node from the end of a singly linked list in one pass (O(n) time, O(1) additional space). If k is larger than the list length, return None. Use Python and explain edge cases (k <= 0, empty list).

Sample Answer

To solve this in one pass with O(1) extra space, use two pointers: advance a "fast" pointer k steps ahead, then advance both "fast" and "slow" together until fast reaches the end. Slow will then point to the k-th node from the end.

python

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

def kth_from_end(head: Node, k: int) -> Node:
    """
    Return the k-th node from the end (1-based). If k <= 0 or k > length or head is None, return None.
    """
    if head is None or k <= 0:
        return None

    fast = head
    # Move fast k steps ahead
    for _ in range(k):
        if fast is None:
            return None  # k larger than length
        fast = fast.next

    slow = head
    # Move both until fast hits the end
    while fast:
        fast = fast.next
        slow = slow.next

    return slow

Key points:- Uses two-pointer (runner) technique; single traversal of list.- Time complexity: O(n), Space complexity: O(1).- Edge cases: - head is None -> returns None. - k <= 0 -> invalid, return None. - k > length -> fast becomes None during initial advance -> return None.- Example: list 1->2->3->4->5, k=2 => returns node with val=4.

EasyTechnical

131 practiced

Write a function in Python to reverse a singly linked list. Provide both an iterative O(n) time O(1) space solution and a recursive solution. For the recursive version, explain the stack usage and the maximum recursion depth for a list of length n. Show the Node class signature you assume.

Sample Answer

Assumed Node class:

python

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

Iterative O(n) time, O(1) space:

python

def reverse_iterative(head: Node) -> Node:
    prev = None
    curr = head
    while curr:
        nxt = curr.next       # save next
        curr.next = prev      # reverse pointer
        prev = curr           # move prev forward
        curr = nxt            # move curr forward
    return prev               # new head

Recursive (O(n) time, O(n) call-stack space):

python

def reverse_recursive(head: Node) -> Node:
    # base: empty or single node
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)  # reverse rest
    head.next.next = head  # make next node point to current
    head.next = None       # detach current
    return new_head

Explanation of stack usage and max recursion depth:- Each recursive call pushes one frame onto the call stack. For a list of length n, there will be n calls in the worst case, so stack usage is O(n).- Maximum recursion depth equals n (or n+1 including the initial call), so for very large lists this can hit Python's recursion limit (default ~1000). For production/data-engine workloads with long streams, prefer the iterative version or increase recursion limit carefully.

Complexity:- Time: O(n) for both.- Space: Iterative O(1) extra; Recursive O(n) extra due to call stack.

Edge cases:- Empty list (head is None)- Single-node list- Very long list (use iterative to avoid recursion limit)

MediumTechnical

83 practiced

Convert a sorted singly linked list to a height-balanced binary search tree (BST) in O(n) time and O(log n) stack space. Implement in Python and explain how you find the middle element without random access. Provide the ListNode and TreeNode class assumptions.

Sample Answer

To build a height-balanced BST from a sorted singly linked list in O(n) time and O(log n) stack space, we avoid repeated middle searches by constructing the BST with an inorder simulation: recursively build the left subtree of size n//2, make the current list node the root, advance the list pointer, then build the right subtree. This uses a global pointer into the list and produces nodes in sorted order.

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

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

Approach and implementation:

python

# build size first
def sortedListToBST(head):
    """
    Convert sorted singly linked list to height-balanced BST.
    O(n) time, O(log n) recursion stack.
    """
    # compute length
    n = 0
    node = head
    while node:
        n += 1
        node = node.next

    # use closure to keep current pointer
    current = head

    def build(l, r):
        nonlocal current
        if l >= r:
            return None
        mid = (l + r) // 2
        # build left subtree
        left = build(l, mid)
        # root is current list node
        root = TreeNode(current.val)
        root.left = left
        current = current.next
        # build right subtree
        root.right = build(mid + 1, r)
        return root

    return build(0, n)

Key points:- We avoid random access by consuming the list in-order: the left recursion constructs the left subtree (first mid elements), then current points to root, then right subtree.- Time: O(n) — each list node visited exactly once.- Space: O(log n) recursion depth for balanced tree (worst O(n) for degenerate).Edge cases: empty list -> None, single node -> single TreeNode.

HardTechnical

87 practiced

You need to merge two large balanced trees (e.g., two BST-based indexes) representing different time ranges into one while maintaining balance. Describe algorithms to perform this merge (in-order traversal to arrays then build balanced tree vs tree-to-tree recursive merges), analyze cost, and suggest which you would pick for minimal downtime and memory use.

Sample Answer

Clarify requirements & constraints:- Two balanced BST-backed indexes A (size n) and B (size m) cover disjoint time ranges; result must be balanced.- Constraints: minimal downtime (index available quickly), minimal extra memory (cannot hold all keys in RAM), large scale (n,m large, possibly on-disk).

Approach 1 — In-order → arrays → build balanced tree1. Do in-order traversal of A and B to produce two sorted streams/arrays (O(n) and O(m)).2. Merge the two sorted arrays into one sorted array (O(n+m) time, O(n+m) space).3. Build a perfectly balanced BST from the merged array by recursive mid-point selection (O(n+m) time).Costs & trade-offs:- Time: O(n+m)- Extra memory: O(n+m) (must store merged array)- Downtime: high if you must block reads/writes while rebuilding; can mitigate by building new tree offline then swap atomically.- Simplicity: simple and guarantees perfect balance.

Approach 2 — Tree-to-tree merge (recursive join/split or bulk-join)Options:- Use join/split primitives for balanced trees (AVL/Red-Black/B-tree). Example: find max of A (or split by separator), then recursively join subtrees; for balanced tree implementations there are O(log n) split/join ops.- Merge by walking smaller tree B and inserting its nodes into A using balanced-tree insert or bulk-insert (amortized cost).Costs & trade-offs:- Time: O(m log((n+m)/n)) more precisely — inserting m items into tree of size ~n costs O(m log((n+m)/n + 1)) ; using join/split primitives you can achieve O(m + log n) in some algorithms if you exploit structure.- Extra memory: O(log n + log m) stack — minimal.- Downtime: can be done online with fine-grained locks or copy-on-write per node (lower downtime).- Complexity: implementation is more complex and depends on tree type.

Practical considerations for large-scale indexes- If indexes are on-disk B-trees or LSM trees, use their native bulk-load or compaction: - B-tree bulk-load from merged sorted stream is O(n+m) I/O with minimal random writes. - LSM: perform compaction/merge between levels, streamed, low memory.- If RAM limited: stream in-order traversal to disk (external merge), then bulk-load into B-tree — external algorithm with O(n+m) I/O and O(1) extra RAM (plus buffers).

Recommendation (minimal downtime + minimal memory):- For very large data and production indexes, prefer a streaming merge + bulk-load/atomic swap: - Stream in-order from both trees (constant-sized buffers), perform external merge on-disk, bulk-load into a new B-tree (or generate SSTables for LSM), then switch pointers/metadata to the new index atomically. - This uses O(1) extra RAM (buffers), O(n+m) I/O, and downtime limited to the atomic swap.- If you must avoid creating a full new index and RAM is extremely constrained but online availability is critical, implement tree-to-tree merge using join/split or incremental inserts with fine-grained locking/COW — minimal extra memory but more complex and potentially slower.

Summary:- In-memory array build: simplest, O(n+m) time, O(n+m) memory, good if memory available and offline rebuild acceptable.- Tree-to-tree incremental/join: low memory, lower downtime if implemented with atomic node-level updates, but more complex and may cost more CPU.- For production large-scale: streaming external merge + bulk-load + atomic swap is the best balance of minimal memory and minimal downtime.

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.