# 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
}
``````

#4

Similar code in Java.

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if(root==null){return result;}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(!stack.isEmpty() || cur!=null){
while(cur!=null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if(cur.right!=null){
cur = cur.right;
}else{
cur = null;
}

}
return result;
}
}
``````