Trying to make a binary search tree, but I keep getting invalid memory address or nil pointer dereference errors

Question

I'm trying to create a BST, add a node, and print the data in that node, but I keep getting invalid memory address or nil pointer dereference errors. I know something is wrong with my pointers, and I've been fiddling around with them all afternoon, and I can't seem to get it right. Could someone please take a look and let me know what stupid mistake I'm making?

package main

import "fmt"

type node struct {
    data  int
    left  *node
    right *node
}

type root struct {
    root *node
}

func (bt root) addNode(n *node, data int) {
    if n == nil {
        newNode := node{
            data:  data,
            left:  nil,
            right: nil,
        }
        n = &newNode
        fmt.Println("Works")
    } else if data < n.data {
        bt.addNode(n.left, data)
    } else {
        bt.addNode(n.right, data)
    }
}

func main() {
    tree := root{root: nil}

    tree.addNode(tree.root, 6)
    fmt.Println(tree.root.data)
}

https://go.dev/play/p/Cps4Y5mqYFM

The assignment n = &newNode in addNode overwrites the contents of the variable n which is an argument to the method and hence is a local variable in it. The result of this assignment is therefore not visible in the caller because the assignment had modified the copy of the caller's variable. Hence tree.root remains nil, which you could have easily seen if you have printed that value. To modify a pointer-typed variable in a function, you has to pass it a pointer to that pointer and derefence it when assigning—like in *ptrToPtr = someAddress. — kostix
– kostix, Commented Apr 26, 2022 at 11:01
To say that in other words, when you call tree.addNode(tree.root) the contents of the variable tree.root, which is nil, is copied into the local variable n of the addNode method, and then that method overwrites the content of that variable. — kostix
– kostix, Commented Apr 26, 2022 at 11:03

Victor · Accepted Answer · 2022-04-26 11:34:57Z

2

As kostix correctly pointed out, in order to modify my tree with that method, I had to pass in a pointer to a pointer to the original tree. Thanks, kostix!

package main

import "fmt"

type node struct {
    data  int
    left  *node
    right *node
}

type root struct {
    root *node
}

func (bt root) addNode(n **node, data int) {
    if *n == nil {
        newNode := node{
            data:  data,
            left:  nil,
            right: nil,
        }
        *n = &newNode
        fmt.Println("Works")
    } else if data < (*n).data {
        bt.addNode(&((*n).left), data)
    } else {
        bt.addNode(&((*n).right), data)
    }
}

func main() {
    tree := root{root: nil}

    tree.addNode(&(tree.root), 6)
    fmt.Println(tree.root.data)
}

answered Apr 26, 2022 at 11:34

Victor

757 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Trying to make a binary search tree, but I keep getting invalid memory address or nil pointer dereference errors

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related