Can the pointer in a struct pointer method be reassigned to another instance?

Question

I've been looking into Golang and have been implementing a few data structures to learn how the language works. I've come across the following issue while writing the code for an AVL tree:

Assigning the primary pointer from a struct pointer method seems to have no effect outside the scope of the function. E.g. tree.rotateLeftToRoot() doesn't result in tree.left becoming the new tree.

Question: Is there a way to reassign the pointer in a struct pointer method in Golang, or is this generally discouraged? In the example this would be the "tree = prevLeft" line.

Code snippet:

//Graphical representation of t.rotateLeftToRoot():
//      t                  L
//   L     R     ->    LL     t
//LL LR                     LR  R
func (tree *AvlTree) rotateLeftToRoot() {
   if tree == nil {
      return
   }
   prevLeft := tree.left
   if prevLeft != nil {
      tree.left = prevLeft.right //tree.left passed root its right branch
      prevLeft.right = tree      //tree becomes tree.left's right branch
      tree.updateHeight()
      prevLeft.updateHeight()
      tree = prevLeft            //desired behaviour: tree.left becomes the new tree
                                 //actual behaviour: no effect when function returns
   }
}

I've tried other combinations of setting the value or address of tree, and none of them had the intended effect. For example, *tree = *prevLeft results in an infinite loop.

Additional note: Returning tree and setting "tree = tree.rotateLeftToRoot()" avoids the issue. This works, but it seems dirty to be mixing effects and requiring assignment to returned values, when the caller really just wants to be able to call a function to update the tree.

Can the tree be set to prevLeft from within the function?

Answer 1

Pointers are values just like let's say int numbers. The difference is the interpretation of that value: pointers are interpreted as memory addresses, and ints are interpreted as integer numbers.

When you want to change the value of a variable of type int, you pass a pointer to that int which is of type *int, and you modify the pointed object: *i = newvalue (the value assigned is an int).

Same goes with pointers: when you want to change the value of a variable of pointer type *int, you pass a pointer to that *int which is of type **int and you modify the pointed object: *i = &newvalue (the value assigned is an *int).

^{Passing a pointer is required because a copy is made from everything you pass, and you could only modify the copy. When you pass a pointer, the same thing happens: a copy is also made of that pointer, but we're not modifying the pointer itself but the pointed value.}

You want to modify a variable of type *AvlTree. In Go the receiver cannot be a pointer to pointer. Spec: Method declarations:

The receiver's type must be of the form T or *T(possibly using parentheses) where T is a type name. The type denoted by T is called the receiver base type; it must not be a pointer or interface type and it must be declared in the same package as the method.

So you have 2 choices:

1. either write a simple function (not method) that takes a **AvlTree and you can pass the address of your tree pointer, so the function can modify the tree pointer (the pointed object)

2. or return the tree pointer from your function/method and have the caller assign it to the variable being the tree pointer.

Addressing your concerns regarding returning the tree pointer: there's nothing wrong with that. Take a look at the builtin function append(): it appends elements to a slice and returns the modified slice. You (the caller) have to assign the returned slice to your slice variable, because append() may modify the slice by allocating a new one if the additional elements do not fit into the original (and since append() takes a non-pointer, the modified value must be returned).

Here's how the solution going with #1 would look like:

func rotateLeftToRoot(ptree **AvlTree) {
    tree := *ptree
    if tree == nil {
        return
    }
    prevLeft := tree.left
    if prevLeft != nil {
        tree.left = prevLeft.right
        prevLeft.right = tree
        tree = prevLeft
    }
    *ptree = tree
}

I've implemented it on the Go Playground to prove it works.

I've used this type:

type AvlTree struct {
    value string
    left  *AvlTree
    right *AvlTree
}

And to easily check the result, I've implemented some methods to produce a string representation:

func (tree *AvlTree) String() string { return tree.str(1) }

func (tree *AvlTree) str(n int) string {
    if tree == nil {
        return "<nil>"
    }
    return fmt.Sprintf("%q\n%s%v,%v\n%s", tree.value, strings.Repeat("\t", n),
        tree.left.str(n+1), tree.right.str(n+1), strings.Repeat("\t", n-1))
}

And this is how a tree is constructed and transformed:

tree := &AvlTree{
    value: "t",
    left: &AvlTree{
        value: "L",
        left: &AvlTree{
            value: "LL",
        },
        right: &AvlTree{
            value: "LR",
        },
    },
    right: &AvlTree{
        value: "R",
    },
}
fmt.Println(tree)
rotateLeftToRoot(&tree)
fmt.Println(tree)

The original tree (without transformation):

"t"
    "L"
        "LL"
            <nil>,<nil>
        ,"LR"
            <nil>,<nil>

    ,"R"
        <nil>,<nil>

And the transformed tree (exactly what you wanted):

"L"
    "LL"
        <nil>,<nil>
    ,"t"
        "LR"
            <nil>,<nil>
        ,"R"
            <nil>,<nil>