0

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...

  • on the first insert the root node will be nil.
  • so the local variable node which references t.root will also be nil
  • the for loop will therefore be skipped.
  • 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?

Kim
  • 3,316
  • 5
  • 25
  • 28

2 Answers2

3
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.

user2357112
  • 260,549
  • 28
  • 431
  • 505
3

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.

Sergio Correia
  • 46
  • 2