Binary Tree Preorder Traversal Problem

Problem Description

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

Example
Given binary tree {1,#,2,3}:

return [1,2,3].

Challenge
Can you do it without recursion?

Solution 1:
Non recursion


   /**
     * @param root: The root of binary tree.
     * @return: Preorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
    	ArrayList<Integer> lst = new ArrayList<Integer>();
    	
    	Stack<TreeNode> stack = new Stack<TreeNode>();
    	
    	if(root != null) stack.push(root);
    	
    	while(!stack.isEmpty()) {
    		TreeNode node = stack.pop();
    		lst.add(node.val);
    		
    		if(node.right != null) {
    			stack.push(node.right);
    		}
    		if(node.left != null) {
    			stack.push(node.left);
    		}
    	}
    	
    	
		return lst;
    }

/**

* @param root: The root of binary tree.

* @return: Preorder in ArrayList which contains node values.

public ArrayList<Integer> preorderTraversal(TreeNode root) {

ArrayList<Integer> lst = new ArrayList<Integer>();

Stack<TreeNode> stack = new Stack<TreeNode>();

if(root != null) stack.push(root);

while(!stack.isEmpty()) {

TreeNode node = stack.pop();

lst.add(node.val);

if(node.right != null) {

stack.push(node.right);

}

if(node.left != null) {

stack.push(node.left);

}

return lst;

}

Solution 2 (recursion – divide & conquer)


    /**
     * @param root: The root of binary tree.
     * @return: Preorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
    	ArrayList<Integer> lst = new ArrayList<Integer>();
    	
    	if(root != null) { 
                lst.add(root.val);
	    	lst.addAll(preorderTraversal(root.left));
	    	lst.addAll(preorderTraversal(root.right));
    	}
    	
		return lst;
    }