package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
	result := []int{}
	if root == nil {
		return result
	}
	inorderTraversalHelper(root, &result)
	return result
}

func inorderTraversalHelper(root *TreeNode, result *[]int) {
	if root.Left != nil {
		inorderTraversalHelper(root.Left, result)
	}
	*result = append(*result, root.Val)
	if root.Right != nil {
		inorderTraversalHelper(root.Right, result)
	}
}

func inorderTraversalIter(root *TreeNode) []int {
	result := []int{}
	stack := []*TreeNode{}
	curr := root
	top := -1
	for curr != nil || top > -1 {
		for curr != nil {
			// push
			stack = append(stack, curr)
			top++
			curr = curr.Left
		}
		if top > -1 {
			curr = stack[top]
			// pop
			stack = stack[:top]
			top--
			result = append(result, curr.Val)
			curr = curr.Right
		}
	}
	return result
}

// func main() {
// 	//        1
// 	//       /
// 	//      2
// 	//     / \
// 	//    3  nil
// 	n3 := TreeNode{3, nil, nil}
// 	n2 := TreeNode{2, &n3, nil}
// 	n1 := TreeNode{1, &n2, nil}
// 	fmt.Println(inorderTraversalIter(&n1))
// }