Start learning free

LESSON 309 OF 414 · LINKED LISTS

Flatten Multilevel List in Rust: Recursive Pre-Order, O(n)

Practice O(n) Recursive Read the full explanation

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not 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, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

 

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation:

The multilevel linked list in the input is as follows:



After flattening the multilevel linked list it becomes:

Example 2:

Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation:

The input multilevel linked list is as follows:

  1---2---NULL
  |
  3---NULL

Example 3:

Input: head = []
Output: []

 

How multilevel linked list is represented in test case:

We use the multilevel linked list from Example 1 above:

 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

The serialization of each level is as follows:

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

To serialize all levels together we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:

[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]

Merging the serialization of each level and removing trailing nulls we obtain:

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

 


Note:

Your algorithm should be recursive and run in O(n · d) time, where d is the maximum nesting depth of the child lists.


STEP 1 OF 8
    Ctrl + Enter to check

    RUST · LINKED LISTS

    Flatten Multilevel List in Rust, explained

    Problem overview

    A multilevel list is a linked list in which any node may also have a child: the head of another list, which can have children of its own. Flattening means producing one single-level order in which each node's child list comes right after the node and before the node's old next sibling.

    In the lesson the structure is not made of pointers. It is a table adj, a slice of (i32, i32) pairs. Nodes are numbered from 1, and the node id doubles as its value. The entry adj[id] is the pair (next, child), and 0 means "no node", which is why ids start at 1. The function flatten(adj, head, result) pushes the flattened ids onto result.

    The example has levels 1-2-3-4-5-6, 7-8-9-10 under node 3 and 11-12 under node 8. The flattened order is [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6]. For 1-2 with node 3 as the child of 1, the order is [1, 3, 2]. An empty list gives an empty result. The statement asks for a recursive solution that runs in O(n).

    Approach: visit the node, then its child, then its next

    The flattened order is a pre-order walk. For a node, first record it, then flatten everything below it through the child, and only then continue with its next sibling. The child's own children and siblings are handled by the same rule, so the problem repeats itself on a smaller structure. That is the shape of a recursive function:

    • if the node is 0, there is nothing to do;
    • push the node;
    • recurse into its child;
    • recurse into its next.

    Doing the child before the next is the entire trick. When the child is flattened first, its whole sub-list lands between the node and the next sibling, which is where the problem wants it. Swapping the two calls would finish each level before descending, and the first example would come out as [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12].

    Each node is visited exactly once, because every node is reachable by exactly one next or child entry. That gives O(n) time.

    Step by step

    1. Declare the helper flatten_level next to flatten. It takes adj: &[(i32, i32)] (only read, so a shared slice is enough), the current id node, and result: &mut Vec<i32>. Because every recursive call receives the same mutable reference, they all append to one vector.
    2. Guard the base case: if node == 0. Id 0 marks a missing node, since real ids start at 1.
    3. Return from that branch without touching result. A function with no return type can end with a bare return;.
    4. Record the node: result.push(node). Pushing before recursing is what makes the order pre-order.
    5. Read the entry: let (next, child) = adj[node as usize];. The slice is indexed with a usize, so the i32 id is cast with as. The pair is Copy, so destructuring it copies two integers.
    6. Recurse into child first, so the sub-list is emitted right after the node.
    7. Recurse into next, which continues the current level after the sub-list.
    8. Delegate from flatten: it just calls Solution::flatten_level(adj, head, result).

    The solution in Rust

    struct Solution;

impl Solution {
    fn flatten_level(adj: &[(i32, i32)], node: i32, result: &mut Vec<i32>) {
        if node == 0 {
            return;
        }
        result.push(node);
        let (next, child) = adj[node as usize];
        Solution::flatten_level(adj, child, result);
        Solution::flatten_level(adj, next, result);
    }

    fn flatten(adj: &[(i32, i32)], head: i32, result: &mut Vec<i32>) {
        Solution::flatten_level(adj, head, result);
    }
}

    Rust details worth knowing:

    • Calling an associated function. Neither function takes self, so they are called through the type: Solution::flatten_level(...). Inside the impl block, Self::flatten_level(...) would mean the same.
    • Passing a &mut down. Passing result to a callee reborrows it for the duration of the call, so the same variable can be passed again on the next line. No clone and no explicit reborrow is needed.
    • The cast as usize. A negative id would wrap to a huge index and the indexing would panic. Valid ids are positive, and 0 is handled before the index is used.
    • Index out of bounds panics. The table needs an entry for every id that can occur, including index 0 for the unused slot, so for ids 1 to 12 the slice has at least 13 entries.
    • The table, not the nodes, is borrowed. There is no ownership puzzle here, which is why the recursion is so short compared with a version built on Box pointers.

    Complexity

    Time: O(n). Every node is pushed once and does a constant amount of work. Calls on the id 0 also cost a constant amount, and there are at most two of them per node.

    Space: O(n) in the worst case. The result holds n ids. On top of that, the call stack grows with the nesting depth of the structure: a chain in which every node is the child of the previous one makes the recursion as deep as the list is long. A chain of 200,000 such nodes overflows the stack and aborts the program. The lesson's iterative version avoids that by keeping its own stack in a vector on the heap.

    Edge cases and common mistakes

    • Empty list. head = 0 hits the base case at once, and result stays empty.
    • No children. A plain list 1-2-3 comes out as [1, 2, 3].
    • Next before child. The output would then keep every level separate, and example 2 would give [1, 2, 3] instead of [1, 3, 2].
    • Pushing after the recursion. That gives a post-order: children before their parent.
    • Forgetting the base case. Without the check on 0, the code would read adj[0] and push 0 into the result, and the recursion would never stop, since the entry at index 0 is (0, 0).
    • Using an id as the table size. The table needs max_id + 1 entries, because index 0 is unused.

    Testing

    • The three-level example, with adj[3] = (4, 7), adj[8] = (9, 11) and the plain next links elsewhere, gives [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6].
    • Node 1 with next 2 and child 3 gives [1, 3, 2].
    • The head 0 gives [].
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free