algorithms_tree.go

package main

import "fmt"

type Node struct {
	Value string
	Left  *Node
	Right *Node
}

func visit(node *Node) {
	fmt.Println(node.Value)
}

func preorder(node *Node) {
	if node == nil {
		return
	}
	visit(node)
	preorder(node.Left)
	preorder(node.Right)
}

func inorder(node *Node) {
	if node == nil {
		return
	}
	inorder(node.Left)
	visit(node)
	inorder(node.Right)
}

func postorder(node *Node) {
	if node == nil {
		return
	}
	postorder(node.Left)
	postorder(node.Right)
	visit(node)
}

func iterativePreorder(node *Node) {
	var s []*Node
	for len(s) > 0 || node != nil {
		if node != nil {
			visit(node)
			if node.Right != nil {
				s = append(s, node.Right)
			}
			node = node.Left
		} else {
			node = s[len(s)-1]
			s = s[:len(s)-1]
		}
	}
}

func iterativeInorder(node *Node) {
	var s []*Node
	for len(s) > 0 || node != nil {
		if node != nil {
			s = append(s, node)
			node = node.Left
		} else {
			node = s[len(s)-1]
			s = s[:len(s)-1]
			visit(node)
			node = node.Right
		}
	}
}

func iterativePostorder(node *Node) {
	var s []*Node
	var lastNodeVisited *Node = nil
	for len(s) > 0 || node != nil {
		if node != nil {
			s = append(s, node)
			node = node.Left
		} else {
			peekNode := s[len(s)-1]
			s = s[:len(s)-1]
			if peekNode.Right != nil && lastNodeVisited != peekNode.Right {
				node = peekNode.Right
			} else {
				visit(peekNode)
				lastNodeVisited = s[len(s)-1]
				s = s[:len(s)-1]
			}
		}
	}
}

func levelOrder(root *Node) {
	if root == nil {
		return
	}

	queue := []*Node{root}
	for len(queue) > 0 {
		visit(queue[0])

		root = queue[0]
		queue = queue[1:]

		if root.Left != nil {
			queue = append(queue, root.Left)
		}
		if root.Right != nil {
			queue = append(queue, root.Right)
		}

	}
}

func main() {
	node := &Node{
		Value: "1",
		Left: &Node{
			Value: "1_2",
			Left: &Node{
				Value: "2_3",
				Left: &Node{
					Value: "3_4",
				},
			},
		},
	}

	fmt.Println("recursive")
	preorder(node)
	inorder(node)
	postorder(node)

	fmt.Println("iterative")
	iterativePreorder(node)
	iterativeInorder(node)
	iterativePostorder(node)

	fmt.Println("level order")
	levelOrder(node)
}

sort.go

package main

import "fmt"

func mergeSort(ary []int) []int {
	if len(ary) <= 1 {
		return ary
	}

	left := mergeSort(ary[0 : len(ary)/2])
	right := mergeSort(ary[len(ary)/2 : len(ary)])
	return merge(left, right)
}

func merge(left []int, right []int) []int {
	var result []int

	for len(left) > 0 && len(right) > 0 {
		if left[0] <= right[0] {
			result = append(result, left[0])
			left = left[1:]
		} else {
			result = append(result, right[0])
			right = right[1:]
		}
	}
	return append(append(result, left...), right...)
}

func insertionSort(ary []int) []int {
	for i, _ := range ary {
		current := ary[i]

		for i > 0 && ary[i-1] > current {
			ary[i] = ary[i-1]
			i = i - 1
		}
		ary[i] = current
	}
	return ary
}

func main() {
	values := []int{1, 2, 3, 1, 2, 3, 4, 7, 1}
	fmt.Println(mergeSort(values))
	fmt.Println(insertionSort(values))
}

https://rosettacode.org/wiki/Tree_traversal#Go
https://en.wikipedia.org/wiki/Tree_traversal