Top Down & Bottom Up Tree Traversal

prefix-postfix.go

package main

import "fmt"

// Node is a named element of a tree witha any number of children
type Node struct {
	Name     string
	Children []Node
}

/*
        root
       /   \
      a     b
     / \   / \
    c  d  e  f
   /
  g
*/
var tree = Node{
	Name: "root",
	Children: []Node{
		{
			Name: "a",
			Children: []Node{
				{Name: "c", Children: []Node{{Name: "g"}}},
				{Name: "d"},
			},
		},
		{
			Name: "b",
			Children: []Node{
				{Name: "e"},
				{Name: "f"},
			},
		},
	},
}

// traverse a tree "top down"
// the "visit" function is just printing the name of the node
func printNamePrefix(tree Node) {
	fmt.Printf("%s ", tree.Name)

	for _, n := range tree.Children {
		printNamePrefix(n)
	}
}

// traverse a tree "bottom up"
// the "visit" function is just printing the name of the node
func printNamePostfix(tree Node) {
	for _, n := range tree.Children {
		printNamePostfix(n)
	}

	fmt.Printf("%s ", tree.Name)
}

/*
	a quick study on tree traversal
	"top down" (prefix order) and "bottom up" (postfix order)
	solid article on the topic that also covers infix traversal:
	https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
*/
func main() {
	fmt.Println("prefix:")
	printNamePrefix(tree)
	fmt.Println("")
	// Output: root a c g d b e f

	fmt.Println("postfix:")
	printNamePostfix(tree)
	fmt.Println("")
	// Output: g c d a e f b root
}