Go Binary Tree Stuff

binarytree.go

package main

import (
	"log"
)

type node struct {
	val        int
	leftChild  *node
	rightChild *node
}

func (n *node) insert(otherNode *node) {
	if otherNode.val > n.val {
		if n.rightChild == nil {
			n.rightChild = otherNode
		} else {
			n.rightChild.insert(otherNode)
		}
	} else {
		if n.leftChild == nil {
			n.leftChild = otherNode
		} else {
			n.leftChild.insert(otherNode)
		}
	}
}

func inOrderTraversal(n *node) {
	if n.leftChild != nil {
		inOrderTraversal(n.leftChild)
	}
	if n.rightChild != nil {
		inOrderTraversal(n.rightChild)
	}
	log.Println(n.val)
}

func levelOrderTraversal(n *node) {
	queue := []*node{n}
	for {
		curNode := queue[0]
		log.Println(curNode.val)
		queue = queue[1:len(queue)]
		if curNode.leftChild != nil {
			queue = append(queue, curNode.leftChild)
		}
		if curNode.rightChild != nil {
			queue = append(queue, curNode.rightChild)
		}
		if len(queue) == 0 {
			break
		}
	}
}

//Erlang like recursion using a list as an accumulator
func levelOrderTraversalRecursive(n *node) {
	levelOrderTraversalRecursiveHelper([]*node{n})
}

func levelOrderTraversalRecursiveHelper(toVisit []*node) {
	if len(toVisit) > 0 {
		n := toVisit[0]
		log.Println(n.val)
		toVisit := toVisit[1:len(toVisit)]

		if n.leftChild != nil {
			toVisit = append(toVisit, n.leftChild)
		}
		if n.rightChild != nil {
			toVisit = append(toVisit, n.rightChild)
		}
		levelOrderTraversalRecursiveHelper(toVisit)
	}
}

func main() {
	root := node{val: 1}
	n1 := &node{val: 14}
	n2 := &node{val: 4}
	n3 := &node{val: 3}
	n4 := &node{val: 90}
	n5 := &node{val: 30}
	n6 := &node{val: 8}
	n7 := &node{val: 18}

	root.insert(n1)
	root.insert(n2)
	root.insert(n3)
	root.insert(n4)
	root.insert(n5)
	root.insert(n6)
	root.insert(n7)

	log.Println("********************")
	inOrderTraversal(&root)
	log.Println("********************")
	levelOrderTraversal(&root)
	log.Println("********************")
	levelOrderTraversalRecursive(&root)
}