Slice always empty after functions gets popped off the stack

Im trying to traverse a tree, and append the values to the slice(Just format printing out the value works), but when i try to append to the slice, i dont get the values, or i get just the root of the tree.

Im not sure how to append to the slice, and make sure the data in it isint lost at the end

package main

import (
	"fmt"
)

type Node struct {
	value int
	left  *Node
	right *Node
}

type BinarySearchTree struct {
	root *Node
}


func (bst *BinarySearchTree) inOderTraversal(currNode *Node) {
	if currNode == nil {
		return
	}

	bst.inOderTraversal(currNode.left)
	
	//trying to append to a slice here, but the slice is always empty after
	//all recursive functions have been popped from the stack
	fmt.Println(currNode.value)
	
	bst.inOderTraversal(currNode.right)
}

How are you appending to a slice? Can you post the code that doesn’t work?

There’re two ways i tried doing it. Option one was ignoring the slice returned by traverse method. Option two is making another function that tries to fix it by returning the slice.
Both options give only the root node, with everything below lost

//1
//this gets just the root node, with other nodes lost
func (bst *BinarySearchTree) inOderTraversal(currNode *Node, list []int) []int {
	if currNode == nil {
		return list
	}

	bst.inOderTraversal(currNode.left, list)
	list = append(list, currNode.value)
	bst.inOderTraversal(currNode.right, list)

	return list
}

//2
//calling this in main. still only gets the root node, with other nodes lost
func (bst *BinarySearchTree) DFSInorder(currNode *Node, list []int) []int{
	return bst.inOderTraversal(currNode, list)
}

func (bst *BinarySearchTree) inOderTraversal(currNode *Node, list []int) []int {
	if currNode == nil {
		return list
	}

	bst.inOderTraversal(currNode.left, list)
	list = append(list, currNode.value)
	bst.inOderTraversal(currNode.right, list)


Slices contain pointers to their underlying arrays, so when you modify their elements, you can see those modifications outside of the function. The slice itself is still conceptually a struct with a pointer to an array plus two other fields tracking the underlying array’s length and capacity. When you write list = append(list, currNode.value), you’re updating the list local variable in your inOderTraversal function, but that isn’t seen by callers of inOderTraversal. Like the append function, itself, you need to return the slice after you append to it for callers to see the appended-to slice.

I acutaly returned the slice in my previous attempts, but the data in it was refreshed every time the function was called.
This one works good. The only down side is that im using a global variable. Does this checkout as the solution?

var inOrderList []int

//DFS (gives everything in order)
func (bst *BinarySearchTree) inOderTraversal(currNode *Node)  {
	if currNode == nil {
		return 
	}

	bst.inOderTraversal(currNode.left)

	inOrderList = append(inOrderList, currNode.value)

	bst.inOderTraversal(currNode.right)
}

My only gripe about this is that it means that you can only have one call to inOderTraversal (is that supposed to be inOrderTraversal?) running at any one time in the whole process. If you have two goroutines running this function, they’ll overwrite each other. I think this might work for you: https://play.golang.org/p/UPvBLHLcr3h

1 Like

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.