Flatten a Multilevel Doubly Linked List

📋

Problem

Imagine you have a complex file system where folders can contain files and other folders nested arbitrarily deep. You want to list all files in a single linear order, flattening the hierarchy.

You are given a doubly linked list where in addition to the next and previous pointers, each node may have a child pointer, which may point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure. Flatten the list so that all the nodes appear in a single-level, doubly linked list. The nodes should appear in the order they are encountered in a depth-first traversal.

1 ≤ Number of nodes ≤ 10^5Node values are integersChild pointers may be nullThe list may be empty (head is null)

Edge cases: Empty list (head is null) → output is nullList with no child pointers → output is the same listList where every node has a child → output is a deeply nested flattened list

</>

IDE

def flatten(head: 'Node') -> 'Node':public Node flatten(Node head)Node* flatten(Node* head)function flatten(head)

def flatten(head):
    # Write your solution here
    pass

class Solution {
    public Node flatten(Node head) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

Node* flatten(Node* head) {
    // Write your solution here
    return nullptr;
}

function flatten(head) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Flattened list missing child nodes or child lists appended at the end onlyGreedy approach that flattens child lists only after traversing next nodes✅ Flatten child lists immediately when encountered before continuing with next nodes

Wrong: Infinite loop or repeated nodes in outputNot clearing child pointers after flattening causing repeated processing✅ Set node.child = null after flattening its child list

Wrong: Broken doubly linked list with incorrect prev pointersNot updating prev pointers when linking child lists✅ Set child.prev = current node and child's last next.prev = original next node

Wrong: Function crashes or returns non-null on empty inputNo base case for null head input✅ Add base case: if head is null, return null immediately

Wrong: Function modifies single node or returns null incorrectlyIncorrect handling of single node with no child✅ Return head immediately if no child or next nodes

✓

Test Cases

Make sure your solution handles empty and single-node lists correctly.

Watch out for greedy approaches and pointer update errors.

Focus on algorithmic complexity and avoid nested loops.

t1_01basic

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":{"val":7,"prev":null,"next":{"val":8,"prev":null,"next":{"val":11,"prev":null,"next":{"val":12,"prev":null,"next":{"val":9,"prev":null,"next":{"val":10,"prev":null,"next":{"val":4,"prev":null,"next":{"val":5,"prev":null,"next":{"val":6,"prev":null,"next":null,"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Starting at head 1, traverse next nodes until 3, then go down child list starting at 7, flattening recursively, then continue with 4, 5, 6.

💡 Think about depth-first traversal of the multilevel list.

💡 Use a stack or recursion to process child lists before continuing with next nodes.

💡 Link child list between current node and next node, then nullify child pointer.

Why it failed: Incorrect flattening order or missing child nodes. Fix by ensuring child lists are inserted immediately after current node before continuing with next nodes. This is the canonical example test.

✓ Correctly flattened the multilevel doubly linked list preserving DFS order.

t1_02basic

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":{"val":4,"prev":null,"next":{"val":5,"prev":null,"next":null,"child":null},"child":null},"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Node 3 has a child list 4->5 which is flattened between 3 and null.

💡 Check if child lists are inserted immediately after their parent node.

💡 Ensure child pointers are set to null after flattening.

💡 Update prev pointers correctly when linking child lists.

Why it failed: Child list not inserted or child pointer not cleared. Fix by linking child list after current node and nullifying child pointer.

✓ Child list correctly flattened and linked.

t2_01edge

Input{"head":null}

Expectednull

⏱ Performance - must finish in 2000ms

Empty list input should return null.

💡 Check if input head is null before processing.

💡 Return null immediately if list is empty.

💡 Avoid dereferencing null pointers.

Why it failed: Function crashes or returns non-null on empty input. Fix by adding base case: if head is null, return null.

✓ Correctly handles empty list input.

t2_02edge

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":null,"child":null}

⏱ Performance - must finish in 2000ms

Single node with no child remains unchanged after flattening.

💡 Test with minimal input of one node.

💡 Ensure function returns the same node if no child exists.

💡 Check that no pointers are incorrectly modified.

Why it failed: Function modifies single node or returns null incorrectly. Fix by returning head immediately if no child or next nodes.

✓ Correctly returns single node unchanged.

t2_03edge

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":5,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":{"val":4,"prev":null,"next":null,"child":null},"child":null},"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Every node has a child, resulting in a deeply nested flattened list preserving DFS order.

💡 Test deep nesting of child pointers.

💡 Ensure recursive or stack-based DFS fully traverses all levels.

💡 Verify child pointers are cleared after flattening.

Why it failed: Partial flattening or missing nested children. Fix by recursively flattening all child lists before continuing.

✓ Correctly flattens deeply nested child lists.

t3_01corner

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":5,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":{"val":4,"prev":null,"next":null,"child":null},"child":null},"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Greedy approach that flattens child lists only when next is null fails here; correct DFS order requires flattening child of 1 before continuing to 2.

💡 Beware of flattening child lists only at the end of next nodes.

💡 Use DFS to flatten child lists immediately after current node.

💡 Insert child list between current node and next node, not after traversing next nodes.

Why it failed: Greedy flattening after next traversal causes incorrect order. Fix by flattening child list immediately when found, before continuing next.

✓ Correct DFS order flattening, not greedy.

t3_02corner

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":null,"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Confusing 0/1 flattening with unbounded: child list must be flattened once per node, not repeatedly or infinitely.

💡 Ensure child lists are flattened exactly once per node.

💡 Avoid loops or repeated flattening of the same child.

💡 Clear child pointer after flattening to prevent reprocessing.

Why it failed: Repeated flattening or infinite loops due to not clearing child pointer. Fix by setting child to null after flattening.

✓ Child pointer cleared and flattened exactly once.

t3_03corner

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":{"val":4,"prev":null,"next":null,"child":null},"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Off-by-one errors in linking prev and next pointers cause broken doubly linked list after flattening.

💡 Carefully update prev pointers when linking child lists.

💡 Check that child's prev points to current node after insertion.

💡 Verify next pointers of last child node link to original next node.

Why it failed: Prev or next pointers not updated correctly causing broken links. Fix by setting child.prev = current and child's last next.prev = original next.

✓ All prev and next pointers correctly updated.

t4_01performance

Input{"head":[1]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000 nodes linked linearly with no children; O(n) expected to complete within 2s.

💡 Use iterative or recursive DFS with O(n) time complexity.

💡 Avoid repeated traversals or nested loops causing O(n^2).

💡 Use stack or recursion carefully to avoid stack overflow.

Why it failed: TLE due to O(n^2) or exponential complexity. Fix by using O(n) DFS or iterative stack approach.

✓ Algorithm runs in O(n) time and passes performance test.

Practice

1. Consider the following code snippet implementing the optimal approach to copy a list with random pointers. Given the input list:
Node1(val=1) -> Node2(val=2) -> Node3(val=3), where Node1.random = Node3, Node2.random = Node1, Node3.random = null.
After Step 2 (assigning random pointers), what is the value of copy_curr.random.val when copy_curr points to the copied node of Node2?

easy

A. None (null)

B. 3

C. 1

D. 2

Solution

1. Step 1: Trace Step 1 (interleaving nodes)

   Original list: 1 -> 2 -> 3 becomes 1 -> 1' -> 2 -> 2' -> 3 -> 3'.

2. Step 2: Trace Step 2 (assign random pointers)

   Node2.random = Node1, so copied Node2 (2') random = Node1.next = 1'. Thus, copy_curr.random.val = 1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   copy_curr.random points to copied Node1 with val=1 [OK]

Hint: Copied node's random points to original.random.next [OK]

Common Mistakes:

• Confusing original and copied nodes when assigning random pointers
• Off-by-one errors in stepping through interleaved list
• Assuming random pointer points to original node's val

2. Consider the following Python code snippet for the MedianFinder class using two heaps. After adding the numbers 1, 5, and 3 in that order, what is the value of the median returned by findMedian()?

easy

A. 1.0

B. 3.0

C. 5.0

D. 2.0

Solution

1. Step 1: Insert 1

   Low heap empty, push -1 to low; low_size=1, high_size=0.

2. Step 2: Insert 5

   5 > -low[0] (which is 1), push 5 to high; low_size=1, high_size=1; heaps balanced.

3. Step 3: Insert 3

   3 <= 5 but > 1, push 3 to high; high_size=2, low_size=1; balance heaps by moving smallest from high (3) to low (-3); low_size=2, high_size=1.

4. Step 4: Find median

   low_size > high_size, median is -low[0] = 3.0.

5. Step 5: Re-examine median calculation

   After balancing, low heap has [-3, -1], high heap has [5]. Median is top of low heap = 3.0, but the question asks for median after adding 1,5,3 in order, so median is 3.0.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Median after [1,5,3] is 3.0 [OK]

Hint: Median is top of larger heap after balancing [OK]

Common Mistakes:

• Forgetting to balance heaps after insertion
• Returning wrong heap top for median

3. What is the time complexity of adding a number and then finding the median using the balanced two heaps approach with lazy deletion for a data stream of size n?

medium

A. O(log n) per addNum and O(log n) per findMedian

B. O(n) per addNum and O(1) per findMedian

C. O(log n) per addNum and O(1) per findMedian

D. O(1) per addNum and O(n) per findMedian

Solution

1. Step 1: Analyze addNum complexity

   Adding a number involves pushing to a heap and balancing heaps, each O(log n) operations.

2. Step 2: Analyze findMedian complexity

   Median is retrieved from the top of heaps without modification, O(1) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Insertion is O(log n), median retrieval O(1) [OK]

Hint: Heap push/pop are O(log n), median peek is O(1) [OK]

Common Mistakes:

• Assuming sorting each query is O(log n)
• Confusing addNum with findMedian complexity

4. Consider the following buggy implementation of SnapshotArray. Which line contains the subtle bug that can cause incorrect get results when multiple sets occur before a snap on the same index?

import bisect

class SnapshotArray:
    def __init__(self, length: int):
        self.snap_id = 0
        self.data = [[(-1, 0)] for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        # Bug here
        self.data[index].append((self.snap_id, val))

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        arr = self.data[index]
        i = bisect.bisect_right(arr, (snap_id, float('inf'))) - 1
        return arr[i][1]

medium

A. Line in snap(): incrementing snap_id before returning

B. Line in __init__(): initializing with (-1, 0) instead of (0, 0)

C. Line in set(): always appending without checking if last snap_id matches

D. Line in get(): using bisect_right instead of bisect_left

Solution

1. Step 1: Analyze set() method

   The set method always appends (snap_id, val) without checking if the last entry has the same snap_id, causing duplicate entries for the same snap_id.

2. Step 2: Consequence on get()

   Duplicate entries for the same snap_id break binary search assumptions and can cause get to return incorrect values.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct code replaces last entry if snap_id matches [OK]

Hint: Check if last snap_id matches before appending in set() [OK]

Common Mistakes:

• Appending blindly causes duplicates
• Misunderstanding initialization defaults

5. Suppose the Twitter design is extended so that users can post the same tweet multiple times (tweet reuse allowed). Which modification to the optimal approach is necessary to correctly handle this scenario?

hard

A. Allow multiple TweetNode instances with the same tweetId but different timestamps in the linked list and heap.

B. Use a hash set to track unique tweetIds per user to avoid duplicates in the feed.

C. Modify the heap to store tweetIds only once, ignoring repeated posts of the same tweetId.

D. Disallow posting duplicate tweetIds by rejecting posts with existing tweetIds.

Solution

1. Step 1: Understand tweet reuse impact

   Allowing duplicate tweetIds means multiple posts with same id but different times must be treated as distinct tweets.

2. Step 2: Adjust data structures

   Each post creates a new TweetNode with unique timestamp; heap and linked lists handle duplicates naturally by time ordering.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Multiple nodes with same tweetId but different times must be stored separately [OK]

Hint: Treat each post as unique by timestamp, even if tweetId repeats [OK]

Common Mistakes:

• Trying to deduplicate tweets in feed incorrectly
• Rejecting duplicate posts unnecessarily