cannot understand recursion part of flatten function-CodePudding

In flatten function I can't understand recursion parts??

2.when flatten return root(not the if section), how root received here?

//below is the code of flatten() which start from end of node .each node have two pointers next and down . This function merge and sort all of them and return them.for help attach full code in last.

        // Java program for flattening a Linked List


        Node flatten(Node root) {
        // Base Cases
        if (root == null || root.right == null)
            return root;

        // recur for list on right
        root.right = flatten(root.right);

        // now merge
        root = merge(root, root.right);

        // return the root
        // it will be in turn merged with its left
        return root;
    }

//full code for help

//flatten inked list full code

// debug in vs studio

   class LinkedList {
    Node head; // head of list
    /* Linked list Node */
    class Node {
        int data;
        Node right, down;

        Node(int data) {
            this.data = data;
            right = null;
            down = null;
        }
    }

    // An utility function to merge two sorted linked lists
    Node merge(Node a, Node b) {
        // if first linked list is empty then second
        // is the answer
        if (a == null)
            return b;

        // if second linked list is empty then first
        // is the result
        if (b == null)
            return a;

        // compare the data members of the two linked lists
        // and put the larger one in the result
        Node result;

        if (a.data < b.data) {
            result = a;
            result.down = merge(a.down, b);
        }

        else {
            result = b;
            result.down = merge(a, b.down);
        }

        result.right = null;
        return result;
    }

    Node flatten(Node root) {
        // Base Cases
        if (root == null || root.right == null)
            return root;

        // recur for list on right
        root.right = flatten(root.right);

        // now merge
        root = merge(root, root.right);

        // return the root
        // it will be in turn merged with its left
        return root;
    }

    /*
     * Utility function to insert a node at beginning of the
     * linked list
     */
    Node push(Node head_ref, int data) {
        /*
         * 1 & 2: Allocate the Node &
         * Put in the data
         */
        Node new_node = new Node(data);

        /* 3. Make next of new Node as head */
        new_node.down = head_ref;

        /* 4. Move the head to point to new Node */
        head_ref = new_node;

        /* 5. return to link it back */
        return head_ref;
    }

    void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data   " ");
            temp = temp.down;
        }
        System.out.println();
    }

    // Driver's code
    public static void main(String args[]) {
        LinkedList L = new LinkedList();

        
        L.head = L.push(L.head, 7);
        L.head = L.push(L.head, 5);

        L.head.right = L.push(L.head.right, 50);
        L.head.right = L.push(L.head.right, 22);
        L.head.right = L.push(L.head.right, 19);

        L.head.right.right = L.push(L.head.right.right, 45);
        L.head.right.right = L.push(L.head.right.right, 40);
        L.head.right.right = L.push(L.head.right.right, 35);
        L.head.right.right = L.push(L.head.right.right, 20);

        // Function call
        L.head = L.flatten(L.head);

        L.printList();
    }

CodePudding user response：

If I understand correctly, you want to know how the recursion works in this code.

1    Node flatten(Node root) {
2        // Base Cases
3        if (root == null || root.right == null)
4            return root;
5
6        // recur for list on right
7        root.right = flatten(root.right);
8
9        // now merge
10        root = merge(root, root.right);
11
12        // return the root
13        // it will be in turn merged with its left
14        return root;
15    }

Let's say our linked list looks like this:

        5 -> 10 -> 19 -> 28
        |    |     |     |
        V    V     V     V
        7    20    22    35
        |          |     |
        V          V     V
        8          50    40
        |                |
        V                V
        30               45

Now, let's traverse this method line by line. The base case ensures that once we reach the right most linked list, it is returned as is. So, now since we passed the above-linked list to this function whose root is not null and has another linked list to its right, function control moves to line 7. On line 7, flatten(root.right) function is called. Let us assume for our sanity, that this function does exactly what it is supposed to and it flattens all the linked lists to its right and we assign this newly flattened right portion of the linked list to root.right.

Now, all we are left with is our base linked list 5-7-8-30 and to its right the flattened linked list. So, we only have to merge these 2 now and return it back which we do in line 10 and 14.

If you, noticed above, I have avoided the hassle of going into the trouble of following the rabbit hole of thinking about function calls on Line 7. This simplifies the recursive logic.

We can think recursively as well and reach to same conclusion because for each subsequent flatten function call, the merge will happen and the root will be returned to the previous function call which will be assigned to root.right in parent function and then merged and returned to its parent function call and the same process will be followed until the control reaches the head of the linked list where only 2 linked lists will remain at the end which will be merged and returned back.

There is a 3rd way to understand this visually with the help of a function callstack diagram. I'll update this answer later to include that when I get some time.