I'd like some help please on how Go pointer receivers work.
I have a contained example below of a binary search tree which hopefully helps me explain.
package main
import "fmt"
type Node struct {
key int
left, right *Node
}
func NewNode(key int) *Node {
return &Node{key, nil, nil}
}
type BST struct {
root *Node
}
func NewBinarySearchTree() *BST {
return &BST{nil}
}
func (t *BST) Insert(key int) {
if t.root == nil {
t.root = NewNode(key)
return
}
var node = t.root
for {
if key < node.key {
if node.left == nil {
node.left = NewNode(key)
return
} else {
node = node.left
}
} else {
if node.right == nil {
node.right = NewNode(key)
return
} else {
node = node.right
}
}
}
}
func inorder(node *Node) {
if node == nil {
return
}
inorder(node.left)
fmt.Print(node.key, " ")
inorder(node.right)
}
func main() {
tree := NewBinarySearchTree()
tree.Insert(3)
tree.Insert(1)
tree.Insert(2)
tree.Insert(4)
inorder(tree.root) // 1 2 3 4
}
After I wrote this, however, I thought I could simplify my insert function as follows:
func (t *BST) Insert2(key int) {
var node *Node
node = t.root
for node != nil {
if key < node.key {
node = node.left
} else {
node = node.right
}
}
node = NewNode(key)
}
However, doing it this way the tree is never updated. My thinking was...
node = NewNode(key) will have the same effect as t.root = NewNode(key)Where does my Insert2 method go wrong? Is there a way it can be tweaked?
You seem to be confusing the usage of pointers.
When you do node = t.root, you merely makes node point to whatever t.root points to.
Later on, when you do node = NewNode(key), you make node points to a newly created item, which is not what you wanted; you want to make t.root point to that new item instead.
Since you intend to modify variables which are of type *Node (root, left and right), we need a pointer to them, so a variable of type **Node, with one more level of indirection.
You can start by making node point to the address of t.root, node := &t.root, then you proceed to your loop.
You can try something like the following:
func (t *BST) Insert3(key int) {
node := &t.root
for *node != nil {
if key < (*node).key {
node = &(*node).left
} else {
node = &(*node).right
}
}
*node = NewNode(key)
}
Pay attention that we use the indirection operator * to access the referenced data, when checking the address on the loop, and also the key.
In the end of the function, *node = NewNode(key) does what you intended to do originally; you are assigning the newly created item to the root, left or right pointers.
node = NewNode(key)
That line doesn't change the tree. That line changes the local variable node; after this line, node points to a different Node, but the object it used to point to is unaffected. To insert into the tree, you have to assign to t.root, node.left, or node.right.