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)
}
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