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
}