# Binary Tree Inorder Traversal

#1

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

```Input: [1,null,2,3]
1
\
2
/
3

Output: [1,3,2]```

Follow up: Recursive solution is trivial, could you do it iteratively?

#2

Recursively adds the node values to the result.

``````func inorderTraversal(root *TreeNode) []int {
result := make([]int, 0)
if root==nil{
return result
}
helper(root, &result)
return result
}

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

``````

#3

The below code uses an explicit stack to do an inorder traversal.

``````type Stack []*TreeNode
func (s *Stack) Push(n *TreeNode) {
*s = append(*s, n)
}
func (s *Stack) Pop() (n *TreeNode) {
x := s.Len() - 1
n = (*s)[x]
*s = (*s)[:x]
return
}
func (s *Stack) Len() int {
return len(*s)
}
func (s *Stack) Peek() *TreeNode {
x := s.Len() - 1
return (*s)[x]
}

func inorderTraversal(root *TreeNode) []int {
result := make([]int, 0)
if root==nil{ return result}
stack := Stack{}
cur := root
for cur!=nil || stack.Len()!=0{
for cur!=nil{
stack.Push(cur)
cur = cur.Left
}

node := stack.Pop()
result = append(result, node.Val)

cur = node.Right
}

return result
}

``````