Why does creating a wrapper object work in Java instead of passing a local reference?

Question

I was looking at this code in Java to convert a sorted linked list to a balanced BST and I wanted to know why implementation #1 doesn't work. What is the Java reason that when I create a wrapper object and pass it around then it works perfectly but when I use the local reference it doesnt ? The objects are still created on the heap right.

Implementation #1

BinaryTree.Node sortedListToBST(MyList.Node w, int start, int end) 
    {
          if (start > end) return null;
          int mid = start + (end - start) / 2;
          BinaryTree.Node left = sortedListToBST(w, start, mid-1);
          BinaryTree.Node parent = new BinaryTree.Node(w.getVal());
          w = w.getNext();
          BinaryTree.Node right = sortedListToBST(w, mid+1, end);
          parent.left = left;
          parent.right =right;
          return parent;
        }



        BinaryTree.Node sortedListToBST(MyList.Node head, int n) {

          return sortedListToBST(head, 0, n-1);
        }

Implementation #2

    BinaryTree.Node sortedListToBSTWrapper(Wrapper w, int start, int end) 
    {
          if (start > end) return null;
          int mid = start + (end - start) / 2;
          BinaryTree.Node left = sortedListToBSTWrapper(w, start, mid-1);
          BinaryTree.Node parent = new BinaryTree.Node(w.node.getVal());
          w.node = w.node.getNext();
          BinaryTree.Node right = sortedListToBSTWrapper(w, mid+1, end);
          parent.left = left;
          parent.right =right;
          return parent;
        }



        BinaryTree.Node sortedListToBSTWrapper(MyList.Node head, int n) {
             Wrapper w = new Wrapper();
                w.node = head;
          return sortedListToBSTWrapper(w, 0, n-1);
        }

Thomas W · Accepted Answer · 2013-05-10T04:16:58.663

4

The key line is:

w.node = w.node.getNext();

In the first implementation, your 'advancing pointer' in the recursive levels is forgotten; parent callers do not see the position having advanced.

If you wanted to make the first approach work, you'd need to carry around an Iterator/ or have the containing class embody an Iterator of some sort, so that advancement thru the source-list while building the LHS would be returned to the parent & used to build the RHS.. before being returned to the grandparent, etc.

If the language had multi-value returns, you could return (BinaryTree.Node, MyList.Node) and use the second field in that tuple to track your work-progress.

Essentially, you've already hacked a solution -- it will be clean & correct if you make W an Iterator, as opposed to an unstructured thing you just munge.

edited May 10 '13 at 04:16

answered May 10 '13 at 04:10

Thomas W

13,940
4
58
76

Thomas, if the object is created on the heap then why don't the parents see the advanced pointers ? – Phoenix May 10 '13 at 16:30
And why does passing a local reference of wrapper which contains another object reference seen by the previous recursive calls ? – Phoenix May 10 '13 at 16:31
Both are references on a stack frame right ? then why does the second approach see things correctly ? Can you illustrate your answer with how the memory is accessed differently even though both are local references ? – Phoenix May 10 '13 at 16:32
Sheesh -- I've given you a correct & detailed answer, you haven't accepted it, and now you're asking me to do your CS homework for you. **Don't sit there and tell me how they're both references on a stack frame, or somesuch rubbish**. I'm not impressed. Accept the answer already, and I might give you a link to an even-more-basic explanation. – Thomas W May 11 '13 at 01:48

Why does creating a wrapper object work in Java instead of passing a local reference?

1 Answers1