package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversalOld(root *TreeNode) []int {
	result := make([]int, 0)
	preorderRecurse(root, &result)
	return result
}

func preorderRecurse(node *TreeNode, result *[]int) {
	if node == nil {
		return
	}
	*result = append(*result, node.Val)
	preorderRecurse(node.Left, result)
	preorderRecurse(node.Right, result)
}

func preorderTraversal(root *TreeNode) []int {
	result := make([]int, 0)
	if root == nil {
		return result
	}
	stack := make([]*TreeNode, 0)
	curr := root
	for len(stack) != 0 || curr != nil {
		for curr != nil {
			result = append(result, curr.Val)
			stack = append(stack, curr)
			curr = curr.Left
		}
		if size := len(stack); size != 0 {
			curr = stack[size-1]
			stack = stack[:size-1]
			curr = curr.Right
		}
	}
	return result
}

// func main() {
// 	t1 := sortedArrayToBST([]int{1, 2, 3, 4, 5, 6, 7})
// 	printTree(t1)
// 	fmt.Println(preorderTraversal(t1))
// }