Binary Tree Preorder Traversal

Preorder: first, visit parent node, then, left child, last is to visit right child.

Algorithm 1 -- DFS & Stack

We can use stack to store left child and right child.

 1 public class Solution {
 2     public ArrayList<Integer> inorderTraversal(TreeNode root) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5          ArrayList<Integer> lst = new ArrayList<Integer>();
 6  
 7         if(root == null)
 8             return lst; 
 9  
10         Stack<TreeNode> stack = new Stack<TreeNode>();
11         //define a pointer to track nodes
12         TreeNode p = root;
13  
14         while(!stack.empty() || p != null){
15  
16             // if it is not null, push to stack
17             //and go down the tree to left
18             if(p != null){
19                 lst.add(p.val);
20                 stack.push(p);
21                 p = p.left;
22             }else{
23                 TreeNode t = stack.pop();
24                 p = t.right;
25             }
26         }
27  
28         return lst;
29     }
30 }

Algorithm 2 -- Recursive

 1 public class Solution {
 2     List<Integer> result = new ArrayList<Integer>();
 3  
 4     public List<Integer> preorderTraversal(TreeNode root) {
 5         if(root != null){
 6             helper(root);
 7         }
 8         return result;
 9     }
10  
11     public void helper(TreeNode p){
12         result.add(p.val);
13         if(p.left!=null)
14             helper(p.left);
15         if(p.right!=null)
16             helper(p.right);
17     }
18 }