binary_tree.go

package main

import (
	"fmt"
	"math/rand"
	"time"
)

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

func NewNode(v int) *Node {
	return &Node{
		value: v,
	}
}

type BinaryTree struct {
	parent *Node
}

func (b *BinaryTree) Insert(n *Node) {
	var recursor func(**Node, *Node)
	recursor = func(p **Node, n *Node) {
		if *p == nil {
			*p = n
			return
		}

		if n.value < (*p).value {
			recursor(&(*p).left, n)
		} else {
			recursor(&(*p).right, n)
		}
	}

	recursor(&(b.parent), n)
}

func (b *BinaryTree) IterAscending(iter func(t *Node)) {
	current := b.parent
	stack := make([]*Node, 0)

	for {
		if current == nil {
			if len(stack) == 0 {
				break
			}

			current = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			iter(current)
			current = current.right
		} else {
			stack = append(stack, current)
			current = current.left
		}
	}
}

func (b *BinaryTree) IterDescending(iter func(t *Node)) {
	var recursor func(*Node)
	recursor = func(n *Node) {
		if n == nil {
			return
		}

		recursor(n.right)
		iter(n)
		recursor(n.left)
	}

	recursor(b.parent)
}

func main() {
	rand.Seed(time.Now().Unix())
	// random number between 100 and 200
	count := int(rand.Float32()*100) + 100
	tree := &BinaryTree{}
	for i := 0; i < count; i++ {
		tree.Insert(NewNode(rand.Intn(count)))
	}

	iterBuilder := func() (func(*Node), func()) {
		elements := make([]int, 0)
		iter := func(n *Node) {
			elements = append(elements, n.value)
		}

		printer := func() {
			fmt.Println(elements)
		}

		return iter, printer
	}

	iter, printer := iterBuilder()
	tree.IterAscending(iter)
	printer()

	iter, printer = iterBuilder()
	tree.IterDescending(iter)
	printer()
}