Constant Space Binary Tree Traversal

package main

import "fmt"

type Node struct {
	val int
	parent *Node
	left *Node
	right *Node
}

func GoLeft(n *Node) *Node {
	return n.left
}

func GoRight(n *Node) *Node {
	return n.right
}

func GoToRightAncestor(n *Node) *Node {
	current := n.parent
	previous := n
	for current.right == nil || current.right == previous {
		previous = current
		current = current.parent
		if current == nil {
			return nil
		}
	}
	return current.right
}

func Visit(n *Node) {
	fmt.Printf("%d ", n.val)
}

// Traverse is the constant space traversal
func Traverse(root *Node) {
	n := root
	for {
		for n.left != nil {
			Visit(n)
			n = GoLeft(n)
		}
		Visit(n)
		if n.right != nil {
			n = GoRight(n)
			continue
		}
		n = GoToRightAncestor(n)
		if n == nil {
			break
		}
	}
	fmt.Println()
}

func _DFSPrint(n *Node) {
	if n.left != nil {
		_DFSPrint(n.left)
	}
	Visit(n)
	if n.right != nil {
		_DFSPrint(n.right)
	}
}

// DFSPrint is a regular binary tree traversal
func DFSPrint(n *Node) {
	_DFSPrint(n)
	fmt.Println()
}

func main() {
	//		1
	//	    2           4
	//   7        8              3
	//      6       9         5
	n6 := &Node{val: 6}
	n9:= &Node{val: 9}
	n5 := &Node{val: 5}
	n3 := &Node{val: 3, left: n5}
	n5.parent = n3
	n7 := &Node{val:7, right: n6}
	n6.parent = n7
	n8 := &Node{val:8, right: n9}
	n9.parent = n8
	n2 := &Node{val:2, left: n7, right: n8}
	n7.parent = n2
	n8.parent = n2
	n4 := &Node{val:4, right: n3}
	n3.parent = n4
	n1 := &Node{val:1, left: n2, right: n4}
	n2.parent = n1
	n4.parent = n1
	DFSPrint(n1)
	Traverse(n1)
}