Searching and Returning a node using recursion in minheap binary tree

Issue

So I am trying to retrieve a node in a minheap tree by index. The way that it would be called is that I would intiatate a empty MinHeapNode struct and pass by its value via &node so that between recursive function calls, if a match was found it would then return. However it seems that even given a found result the newly assigned empty node would be overwritten by another recursive call that has an empty version of that node. I’m still getting used to the idea of pointers and addresses so I believed that passing the values address would get around this since it would be calling the same value at the same address between calls. But apparently this is something is not correct.

type MinHeapNode struct {
    Parent *MinHeapNode
    Left   *MinHeapNode
    Right  *MinHeapNode
    Value  int
    Index  int
}

func (MHN *MinHeapNode) Insert(value int) {

    if !MHN.hasLeftChild() {
        MHN.Left = &MinHeapNode{Parent: MHN, Value: value}
        return
    }

    if !MHN.hasRightChild() {
        MHN.Right = &MinHeapNode{Parent: MHN, Value: value}
        return
    }

    if MHN.hasLeftChild(){
        MHN.Left.Insert(value)
        return
    }

    if MHN.hasRightChild(){
        MHN.Right.Insert(value)
        return
    }
}
func (MHN *MinHeapNode) setIndex(count *int){

    index := *count
    *count = *count +1
    MHN.Index = index

    if MHN.hasLeftChild(){
        MHN.Left.setIndex(count)
    }
    
    if MHN.hasRightChild(){
        MHN.Right.setIndex(count)
    }
    
}


func (MHN *MinHeapNode) getIndex(index int, node *MinHeapNode){
    if MHN == nil{
        return
    }

    if MHN.Index == index{
        node = MHN
        return
    }
        MHN.Left.getIndex(index, node)
        MHN.Right.getIndex(index,node)
    }
}

type MinHeapTree struct {
    Root MinHeapNode
    Size int
}

func (MHT *MinHeapTree) getIndex(index int)(*MinHeapNode, error){
    if MHT.Size < index +1 {
        err := fmt.Errorf("index exceeds tree size")
        return nil, err
    } 
    var node MinHeapNode
    MHT.Root.getIndex(index, &node)
    return &node, nil

}

Solution

The issue you are facing appears to be with the statement node = MHN in getIndex (but as your code is incomplete I cannot confirm if this is the only issue).

node = MHN will update the value of node (a parameter, so passed by value and, its scope is the function body). This has no impact on the value of the MinHeapNode that node pointed to at the start of the function. To correct this use *node = *MHN.

This can be demonstrated with a simple program (playground)

type MinHeapNode struct {
    Test string
}

func getIndexBad(node *MinHeapNode) {
    newNode := MinHeapNode{Test: "Blah"}
    node = &newNode
}

func getIndexGood(node *MinHeapNode) {
    newNode := MinHeapNode{Test: "Blah"}
    *node = newNode
}
func main() {
    n := MinHeapNode{}
    fmt.Println(n)
    getIndexBad(&n)
    fmt.Println(n)
    getIndexGood(&n)
    fmt.Println(n)
}

The output demonstrates that the "bad" function does not update the passed in node:

{}
{}
{Blah}

Answered By – Brits

Answer Checked By – Dawn Plyler (GoLangFix Volunteer)

Leave a Reply

Your email address will not be published.