1

I have tried implementing the code for Sorted Linked List to BST from leetcode https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/ .

The approach which I have used to use a recursive approach like below. But here we have to use reference (&) in head in the function argument. If I don't use, then output will not be correct and gives wrong answer. I am not able to grasp why reference to head is needed here or in what type of recursion scenarios we should do that. I sometimes get confused in recursion.

int countNodes(ListNode* head) {
    int count = 0;
    ListNode *temp = head;
    
    while (temp != NULL) {
        temp = temp->next;
        count++;
    }
    return count;
}

TreeNode *sortedListUtil(ListNode *&head, int n) { 
    // head should be ref, if we dont use & , 
    //   unexpected output will come
    if (n <= 0)
        return NULL;
    
    TreeNode *left = sortedListUtil(head, n/2);
    
    TreeNode *root = new TreeNode(head->val);
    
    root->left = left;
    head = head->next;
    
    root->right = sortedListUtil(head, n - n/2 -1); 
        // recur for remaining nodes
    
    return root;
}

TreeNode* sortedListToBST(ListNode* head) {
    if (head == NULL)
        return NULL;
    
    int n = countNodes(head);
    return sortedListUtil(head, n);
}

Input linked List is : head = [-10,-3,0,5,9]
Output of BST should be this if I use & in head in function argument : [0,-3,9,-10,null,5]

If I don't use '&' in function argument then the tree constructed will be :

[-10,-10,-3,-10,null,-3] which is wrong. Root Node should be 0.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Nerd
  • 43
  • 7
  • None of this code produces any output, so when you say "output is not correct" we have no idea what you're talking about. A proper [mcve] would go a *long* way to identify what is wrong if you do *not* use a reference. Regarding that, if any caller of `sortedListUtil`, *including itself*, expects the argument to `head` to be modified, a reference is required since you obviously can't exploit using the function return value (you're already using it for something else). – WhozCraig Nov 23 '20 at 07:45
  • I've re-tagged. see the "reference" tag info and questions for more. – Will Ness Nov 23 '20 at 08:16

1 Answers1

1

sortedListUtil does two things: it returns the root (1), and it also changes the head (2) so that its invocations are advancing along the list from call to the other recursive call:

TreeNode *sortedListUtil(ListNode *&head, int n) { 
    // head should be ref, if we dont use & , 
    //   unexpected output will come
    if (n <= 0)
        return NULL;
    
    TreeNode *left = sortedListUtil(head, n/2);
    
    TreeNode *root = new TreeNode(head->val);  // <<<<------ NB (3)
    
    root->left = left;
    head = head->next;  // <<<<--------------------- NB (2)
    
    root->right = sortedListUtil(head, n - n/2 -1); 
        // recur for remaining nodes
    
    return root;        // <<<<--------------------- NB (1)
}

Without changing the head, each invocation of sortedListUtil would look at the same element in the input linked list -- its head element.

But this way, for each element that is put into a ListNode by TreeNode *root = new TreeNode(head->val); (3), the head is advanced so that the next element from the list will be the one that gets put into the next constructed ListNode.

Since head is function's parameter, it must be passed by reference & so the change is seen by the caller; otherwise the variable would be local to the function invocation and the change would not be seen by the caller.

Since we've used the list's element, we must advance the pointer into the list, so that the next list's element is the one that goes next into the next node.

edit: Where does a given sortedListUtil invocation change head? How many times? Just once! So whatever is done within the "left" invocation(s), the head is advanced; then we take one element (the one we're at, after the left is filled), advance head one notch accordingly, and let the "right" invocation(s) fill the right subtree!

Recursion works like this: assume it works; conclude it works for the smaller case(s) (here, left and right) by the hypothesis (and also, for the smallest case -- where we just return NULL and do not touch the head); see that adding small change by this invocation doesn't break things (it doesn't, we properly advance head one notch); then conclude it works overall!

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • Thanks for the explanation, but still not very clear. I am advancing head by head -> next, but why & is needed. like whenever generally when we call recursively we do fun(root->right) , we don't use ampersand – Nerd Nov 23 '20 at 08:08
  • this is how function parameters and passing by reference work. without reference you get just local variable. you change it by `head = (head -> next)`, but what you are changing is the variable local to the function. it must be passed by reference so that what's changed is the variable that the _caller_ used when it made the fucntion call: `foo( head, ... )`. – Will Ness Nov 23 '20 at 08:11
  • e.g., `int foo( int i ) { j = i; j = j+1; }`. `j` is changing, but the caller of `int i = 0; foo(i);` doesn't see the change, why, it's `j`, you say, it's a new local variable inside `foo`. right. but the parameter `i` is also local just in the same way. – Will Ness Nov 23 '20 at 08:13
  • only if we pass it by reference, `into foo( int& i) { i = i+1; }`, then `{... ; int i = 0; foo(i); /* now i is 1! */ }` – Will Ness Nov 23 '20 at 08:14
  • I got this example, but I get confused with these types of recursion scenarios. when there are more than 1 recursive call one after the other and we do something in between/after those calls. – Nerd Nov 23 '20 at 08:16
  • where does the function change `head`? how many times? just once! so whatever is done with the "left" invocation, the head is advanced; then we take _one_ element (the one we're at, after the left is filled), advance `head` one notch accordingly, and let "right" invocation to fill the right subtree. recursion works like this: assume it works; conclude it works for the smaller case(s) (here, left and right); see that adding small change by _this invocation_ doesn't break things (it doesn't, we properly advance `head` one notch); **then** conclude it works overall! – Will Ness Nov 23 '20 at 08:18
  • see [this](https://stackoverflow.com/a/27804489/849891) for general description of what recursion is, at the bottom of the answer. also I invite you to search for my answers on "recursion" tag for more verbiage. :) – Will Ness Nov 23 '20 at 08:25