tree.go

package main

import (
	"fmt"
)

type NodeTree struct {
	Value int
	Left  *NodeTree
	Right *NodeTree
}

type NodeTreeImpl interface {
	Visit()
}

type StackNode struct {
	Value interface{}
	Next  *StackNode
}

type Stack struct {
	Head *StackNode
	Size int
}

type StackImpl interface {
	Push(interface{})
	Pop() interface{}
	Peek() interface{}
	IsEmpty() bool
}

func (s *Stack) Push(value interface{}) {
	newNode := &StackNode{value, s.Head}
	s.Head = newNode
	s.Size++
}

func (s *Stack) Pop() interface{} {
	if s.IsEmpty() {
		return nil
	}

	value := s.Head.Value
	s.Head = s.Head.Next
	s.Size--
	return value
}

func (s *Stack) IsEmpty() bool {
	return s.Size == 0
}

func (s *Stack) Peek() interface{} {
	if s.IsEmpty() {
		return nil
	}
	return s.Head.Value
}

func (s *Stack) Traverse(node *StackNode, fn func(value interface{})) {
	if node != nil {
		fn(node.Value)
		s.Traverse(node.Next, fn)
	}
}

func main() {
	t := &NodeTree{
		Value: 1,
		Left: &NodeTree{
			Value: 2,
			Left: &NodeTree{
				Value: 3,
				Right: &NodeTree{
					Value: -4,
					Right: &NodeTree{
						Value: -54,
						Right: &NodeTree{
							Value: -64,
						},
					},
				},
			},
			Right: &NodeTree{
				Value: 5,
			},
		},
		Right: &NodeTree{
			Value: 6,
			Left: &NodeTree{
				Value: 7,
			},
			Right: &NodeTree{
				Value: 8,
			},
		},
	}

	stack := new(Stack)
	curr := t

	for curr != nil || !stack.IsEmpty() {
		for curr != nil {
			stack.Push(curr)
			curr = curr.Left
		}

		curr = stack.Peek().(*NodeTree)
		stack.Pop()

		fmt.Println(curr.Value)

		curr = curr.Right

	}
}