Go implementation of binary tree data structure with methods for traversal and finding lowest common ancestor for nodes.

binary_tree_traversal.go

package main

import (
	"fmt"
	"strconv"
	"strings"
)

type Node struct {
	Data   interface{}
	Parent *Node
	Left   *Node
	Right  *Node
}

func (n *Node) TraverseBreadthFirst(handler func(*Node)) {
	nodes := make([]*Node, 0) // half-assed queue
	nodes = append(nodes, n)
	idx := 0
	left := 1

	for left > 0 {
		current := nodes[idx]
		left--
		idx++

		handler(current)

		if current.Left != nil {
			left++
			nodes = append(nodes, current.Left)
		}

		if current.Right != nil {
			left++
			nodes = append(nodes, current.Right)
		}
	}
}

func (n *Node) TraversePreOrder(handler func(*Node)) {
	if n == nil {
		return
	}
	handler(n)
	n.Left.TraversePreOrder(handler)
	n.Right.TraversePreOrder(handler)
}

func (n *Node) TraverseInOrder(handler func(*Node)) {
	if n == nil {
		return
	}
	n.Left.TraverseInOrder(handler)
	handler(n)
	n.Right.TraverseInOrder(handler)
}

func (n *Node) TraversePostOrder(handler func(*Node)) {
	if n == nil {
		return
	}
	n.Left.TraversePostOrder(handler)
	n.Right.TraversePostOrder(handler)
	handler(n)
}

func LowestCommonAncestor(x, y, root *Node) *Node {
	xAncestors := make([]*Node, 0)
	yAncestors := make([]*Node, 0)

	xAncestors = append(xAncestors, x)
	yAncestors = append(yAncestors, y)

	last := func(s []*Node) *Node {
		return s[len(s)-1]
	}

	for last(xAncestors) != root {
		xAncestors = append(xAncestors, last(xAncestors).Parent)
	}

	for last(yAncestors) != root {
		yAncestors = append(yAncestors, last(yAncestors).Parent)
	}

	for _, m := range xAncestors {
		for _, n := range yAncestors {
			if m == n {
				return m
			}
		}
	}

	return nil
}

func LowestCommonAncestorNoParentPointer(x, y, root *Node) *Node {
	parents := make(map[*Node]*Node)
	parents[root] = nil

	root.TraversePreOrder(func(n *Node) {
		if n.Left != nil {
			parents[n.Left] = n
		}

		if n.Right != nil {
			parents[n.Right] = n
		}
	})

	ancestorsOf := func(n *Node) []*Node {
		ancestors := make([]*Node, 0)

		for a := n; a != nil; a = parents[a] {
			ancestors = append(ancestors, a)
		}

		return ancestors
	}

	xAncestors := ancestorsOf(x)
	yAncestors := ancestorsOf(y)

	for _, m := range xAncestors {
		for _, n := range yAncestors {
			if m == n {
				return m
			}
		}
	}

	return nil
}

func main() {
	var node01, node02, node03, node04, node05, node06, node07, node08, node09, node10, node11, node12, node13, node14, node15, node16 Node

	node01 = Node{Data: 1, Left: &node02, Right: &node03}
	node02 = Node{Data: 2, Left: &node04, Right: &node05, Parent: &node01}
	node03 = Node{Data: 3, Left: &node06, Right: &node07, Parent: &node01}
	node04 = Node{Data: 4, Left: &node08, Right: &node09, Parent: &node02}
	node05 = Node{Data: 5, Parent: &node02}
	node06 = Node{Data: 6, Left: &node10, Right: &node11, Parent: &node03}
	node07 = Node{Data: 7, Parent: &node04}
	node08 = Node{Data: 8, Left: &node12, Right: &node13, Parent: &node04}
	node09 = Node{Data: 9, Left: &node14, Right: &node15, Parent: &node04}
	node10 = Node{Data: 10, Left: &node16, Parent: &node06}
	node11 = Node{Data: 11, Parent: &node06}
	node12 = Node{Data: 12, Parent: &node08}
	node13 = Node{Data: 13, Parent: &node08}
	node14 = Node{Data: 14, Parent: &node09}
	node15 = Node{Data: 15, Parent: &node09}
	node16 = Node{Data: 16, Parent: &node10}

	asciiTree := `
         ____1____
        /         \
       2           3
      / \         / \
    _4_  5      _6_  7
   /   \       /   \
  8     9    10    11
 / \   / \   /
12 13 14 15 16
`

	d := make([]string, 0)

	handler := func(n *Node) {
		d = append(d, strconv.Itoa(n.Data.(int)))
	}

	fmt.Print(asciiTree)

	fmt.Println()
	fmt.Println("Traversals:")

	t := &node01

	t.TraversePreOrder(handler)
	fmt.Printf("\t%-14s %s\n", "pre-order:", strings.Join(d, " -> "))

	d = make([]string, 0)
	t.TraverseInOrder(handler)
	fmt.Printf("\t%-14s %s\n", "in-order:", strings.Join(d, " -> "))

	d = make([]string, 0)
	t.TraversePostOrder(handler)
	fmt.Printf("\t%-14s %s\n", "post-order:", strings.Join(d, " -> "))

	d = make([]string, 0)
	t.TraverseBreadthFirst(handler)
	fmt.Printf("\t%-14s %s\n", "breadth-first:", strings.Join(d, " -> "))

	fmt.Println()
	fmt.Println("Finding common ancestors:")

	fmt.Printf("\tlowest common ancestor of 8 and 14: %d\n", LowestCommonAncestor(&node08, &node14, &node01).Data)
	fmt.Printf("\tlowest common ancestor of 8 and 13: %d\n", LowestCommonAncestor(&node08, &node13, &node01).Data)
	fmt.Printf("\tlowest common ancestor of 12 and 16: %d\n", LowestCommonAncestor(&node12, &node16, &node01).Data)

	fmt.Println()
	fmt.Println("Finding common ancestors (not using parent pointer):")

	fmt.Printf("\tlowest common ancestor of 8 and 14: %d\n", LowestCommonAncestorNoParentPointer(&node08, &node14, &node01).Data)
	fmt.Printf("\tlowest common ancestor of 8 and 13: %d\n", LowestCommonAncestorNoParentPointer(&node08, &node13, &node01).Data)
	fmt.Printf("\tlowest common ancestor of 12 and 16: %d\n", LowestCommonAncestorNoParentPointer(&node12, &node16, &node01).Data)
}