// Week 14 – Traversal without recursion, with an own stack
// Run: go run ./w14/iterative
package main

import "fmt"

type Node struct {
	Value       rune
	Left, Right *Node
}

func leaf(v rune) *Node { return &Node{Value: v} }

func preorder(root *Node) {
	st := []*Node{}
	if root != nil {
		st = append(st, root)
	}
	for len(st) > 0 {
		p := st[len(st)-1]
		st = st[:len(st)-1]
		fmt.Printf("%c ", p.Value)
		if p.Right != nil { // the right one first, so that the left one comes out first
			st = append(st, p.Right)
		}
		if p.Left != nil {
			st = append(st, p.Left)
		}
	}
	fmt.Println()
}

func inorder(root *Node) {
	var st []*Node
	p := root
	for p != nil || len(st) > 0 {
		for p != nil {
			st = append(st, p)
			p = p.Left
		}
		p = st[len(st)-1]
		st = st[:len(st)-1]
		fmt.Printf("%c ", p.Value)
		p = p.Right
	}
	fmt.Println()
}

func main() {
	root := &Node{'F', &Node{'B', leaf('A'), &Node{'D', leaf('C'), leaf('E')}}, &Node{'G', nil, &Node{'I', leaf('H'), nil}}}
	fmt.Print("preorder (stack): ")
	preorder(root)
	fmt.Print("inorder (stack):  ")
	inorder(root)
}