Binary Tree Preorder Traversal


#1

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

Example:

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

Output: [1,2,3]

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


#2

The below code uses a recursive approach to traverse and collect the values from all nodes in the binary tree.

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

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

#3

The below code uses an explicit stack to control the tree traversal and collect the values at each node.

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 preorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    stack := &Stack{}
    cur := root
    for cur!=nil || stack.Len()!=0{
        for cur!=nil{
            result = append(result, cur.Val)
            stack.Push(cur)
            cur = cur.Left
        }
        
        node := stack.Pop()
        cur = node.Right
    }
    
    return result
}