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

95 practiced

Given two sorted singly linked lists, implement merge_two_sorted_lists(l1, l2) in Python that returns a merged sorted list by reusing node pointers. Implement iteratively in O(n + m) time and O(1) extra space. Show example l1 = 1->3->5 and l2 = 2->4 and resulting list.

Sample Answer

To merge two sorted singly linked lists in-place iteratively, use a dummy head and advance pointers by reusing existing nodes (no new node allocations). Walk both lists, attach the smaller node to the tail, advance that list's pointer, and continue until one list is exhausted—then attach the remaining part.

python

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

def merge_two_sorted_lists(l1, l2):
    """
    Merge two sorted singly linked lists in-place.
    Time: O(n + m), Space: O(1)
    Returns head of merged list.
    """
    dummy = ListNode(-1)   # temporary starter
    tail = dummy

    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
        tail.next = None  # detach to avoid accidental cycles

    # attach remaining nodes (one of l1 or l2 may be non-empty)
    tail.next = l1 if l1 else l2
    return dummy.next

# Example:
# l1: 1->3->5
l1 = ListNode(1, ListNode(3, ListNode(5)))
# l2: 2->4
l2 = ListNode(2, ListNode(4))

merged = merge_two_sorted_lists(l1, l2)

# Print result
out = []
cur = merged
while cur:
    out.append(str(cur.val))
    cur = cur.next
print("->".join(out))  # Output: 1->2->3->4->5

Key points:- Uses only existing nodes (O(1) extra space).- Deterministic O(n+m) time: each node visited once.- Edge cases: one or both lists empty; duplicate values handled by <= branch.- Alternative: recursive merge (elegant but uses O(n+m) call stack).

EasyTechnical

88 practiced

Implement reverse_list_recursive(head) in Python to reverse a singly linked list using recursion. Explain base case and how recursion rewires pointers during unwinding. Discuss recursion depth limits, stack usage and space complexity compared to iterative solution and how to mitigate stack overflow for long lists.

Sample Answer

To reverse a singly linked list recursively, we recurse to the list tail, then as recursion unwinds we rewire pointers: node.next.next = node and node.next = None. Base case is empty list or single node — already reversed.

python

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

def reverse_list_recursive(head):
    """
    Reverse singly linked list using recursion.
    Returns new head.
    """
    # Base case: empty or single node
    if head is None or head.next is None:
        return head

    # Recurse: reverse the rest of the list
    new_head = reverse_list_recursive(head.next)

    # Unwinding step: head.next is tail of reversed sublist
    head.next.next = head  # point tail back to current head
    head.next = None       # current head becomes new tail

    return new_head

Key points:- Base case: head is None or head.next is None — nothing to reverse.- During unwinding: for node A -> B, after reversing B..end, set B.next (which becomes tail of reversed suffix) to A, and A.next = None.- Time: O(n); Space: O(n) call stack. Iterative two-pointer approach uses O(1) extra space and avoids recursion.- Python recursion depth: default ~1000. For lists longer than recursion limit you risk RecursionError / stack overflow.Mitigations:- Use iterative reverse for long lists.- If you must use recursion, increase recursion limit (sys.setrecursionlimit) carefully and ensure available C stack, or implement reversal using an explicit stack/loop.

EasyTechnical

78 practiced

Implement two methods for a singly linked list in Python: insert_head(value) and insert_tail(value). Provide a LinkedList class that maintains head and optionally tail pointer. Explain time complexity for each operation and show how maintaining a tail pointer enables O(1) tail insertion. Include handling of empty list and edge cases.

Sample Answer

To implement insert_head and insert_tail efficiently, keep a head pointer always and a tail pointer to enable O(1) appends. insert_head is always O(1). insert_tail is O(1) when a tail pointer exists, otherwise O(n) because you must traverse to the end.

python

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

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None  # maintain tail for O(1) inserts at end

    def insert_head(self, value):
        """Insert new node at the beginning. O(1) time."""
        node = Node(value)
        node.next = self.head
        self.head = node
        # If list was empty, tail should also point to the new node
        if self.tail is None:
            self.tail = node

    def insert_tail(self, value):
        """Insert new node at the end. O(1) time because we maintain tail."""
        node = Node(value)
        if self.tail is None:
            # empty list: head and tail become the new node
            self.head = node
            self.tail = node
        else:
            # append after tail and move tail pointer
            self.tail.next = node
            self.tail = node

    def to_list(self):
        """Helper to visualize list contents."""
        out = []
        cur = self.head
        while cur:
            out.append(cur.value)
            cur = cur.next
        return out

Key points:- insert_head: O(1) time, O(1) space. Handles empty list by setting tail when head was None.- insert_tail with tail pointer: O(1) time, O(1) space. Without tail pointer you'd need O(n) time to find the last node.- Edge cases covered: inserting into empty list, inserting into single-element list, and maintaining invariants (tail.next is always None).

EasyTechnical

69 practiced

Implement insert_bst(root, value) iteratively in Python to insert a value into a binary search tree and return the updated root. Explain time complexity O(h) where h is height, and show behavior for empty tree, duplicates and deep unbalanced trees.

Sample Answer

To insert into a BST iteratively, traverse from root tracking parent until you find a null child where the new node belongs. This is O(h) time because you follow one root→leaf path of length at most the tree height h; space is O(1) since no recursion/extra structures are used.

python

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

def insert_bst(root, value):
    """Iterative BST insertion. Returns updated root."""
    new_node = TreeNode(value)
    if root is None:
        return new_node  # empty tree -> new node becomes root

    cur = root
    parent = None
    while cur:
        parent = cur
        if value < cur.val:
            cur = cur.left
        elif value > cur.val:
            cur = cur.right
        else:
            # Duplicate handling: here we do nothing and return original root.
            # Alternatives: allow duplicates on one side (e.g., right) or maintain count.
            return root

    # attach new_node as appropriate child of parent
    if value < parent.val:
        parent.left = new_node
    else:
        parent.right = new_node
    return root

Behavior notes:- Empty tree: returns new node as root.- Duplicates: current implementation ignores duplicates (no change). You can alternatively store a count or always insert duplicates to one side.- Deep unbalanced trees: height h could be O(n) worst-case (sorted inserts), so insertion becomes O(n). To avoid this use self-balancing trees (AVL/Red-Black) or randomize insert order.

HardTechnical

73 practiced

Implement conversion functions between a general rooted tree where each node has a list of children and its left-child right-sibling binary tree representation. Provide convert_to_lcrs(root) and convert_from_lcrs(root) in Python. Discuss advantages of this representation for storage, recursion and applications in NLP parse trees or XML processing.

Sample Answer

Approach: represent the general tree Node with .val and .children (list). Represent LCRS binary Node with .val, .left (first child), .right (next sibling). convert_to_lcrs does a recursive transform: for each general node, create a binary node; its left points to the LCRS-converted first child (and that child's right chain links the siblings). convert_from_lcrs reverses that: reconstruct the children list by walking left child and following rights.

python

class TreeNode:
    def __init__(self, val, children=None):
        self.val = val
        self.children = children or []

class LCRSNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left    # first child
        self.right = right  # next sibling

def convert_to_lcrs(root: TreeNode) -> LCRSNode:
    if root is None:
        return None
    node = LCRSNode(root.val)
    if root.children:
        # convert first child and attach as left
        node.left = convert_to_lcrs(root.children[0])
        # convert siblings and chain via right pointers
        cur = node.left
        for child in root.children[1:]:
            cur.right = convert_to_lcrs(child)
            cur = cur.right
    return node

def convert_from_lcrs(root: LCRSNode) -> TreeNode:
    if root is None:
        return None
    node = TreeNode(root.val)
    # reconstruct children by walking left then rights
    child = root.left
    while child:
        node.children.append(convert_from_lcrs(child))
        child = child.right
    return node

Key points:- Time: O(n) visiting each node once. Space: O(h) recursion stack (h = height).- Handles empty trees, single node, arbitrary arity.- Advantages: compact binary-pointer storage (two pointers per node), reuse of binary-tree algorithms and recursion patterns, simpler pointer-based traversals. Useful for streaming/parsing XML or NLP parse trees where node arity varies — you can run binary tree traversals, map subtree operations, or serialize reliably. In NLP, LCRS simplifies tree-linearization, incremental parsing, and memory-efficient storage when many variable-arity nodes exist.- Trade-offs: sibling chaining makes some operations (e.g., random access to k-th child) O(k) rather than O(1).

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.