package main

import "fmt"

type node struct {
	val   int
	left  *node
	right *node
}

func main() {
	n8 := node{8, nil, nil}
	n7 := node{7, nil, nil}
	n6 := node{6, &n7, &n8}
	n5 := node{5, nil, nil}
	n4 := node{4, nil, &n6}
	n3 := node{3, nil, &n5}
	n2 := node{2, &n4, nil}
	n1 := node{1, &n2, &n3}
	fmt.Println("preorder: ")
	preorder(&n1)
	fmt.Println("\ninorder: ")
	inorder(&n1)
	fmt.Println("\npostorder: ")
	postorder(&n1)
	fmt.Println("\nlevelorder: ")
	levelorder(&n1)
	fmt.Println()
}

func preorder(root *node) {
	if root == nil {
		return
	}
	fmt.Printf("%d ", root.val)
	preorder(root.left)
	preorder(root.right)
}

func inorder(root *node) {
	if root == nil {
		return
	}
	inorder(root.left)
	fmt.Printf("%d ", root.val)
	inorder(root.right)
}

func postorder(root *node) {
	if root == nil {
		return
	}
	postorder(root.left)
	postorder(root.right)
	fmt.Printf("%d ", root.val)
}

func levelorder(root *node) {
	if root == nil {
		return
	}
	queue := make([]*node, 0)
	queue = append(queue, root)
	for len(queue) != 0 {
		head := queue[len(queue)-1]
		queue = queue[:len(queue)-1]
		fmt.Printf("%d ", head.val)
		if head.left != nil {
			queue = append(queue, head.left)
		}
		if head.right != nil {
			queue = append(queue, head.right)
		}
	}
}