import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.lang.Integer;
import java.lang.String;
 
public class BinaryTreeLintcode {



/*Definition for binary tree*/
	public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

//Global Var
TreeNode root;

//Consturctor
    public BinaryTreeLintcode(char[] tree) {
        root = buildBinaryTree(tree, 1);
    }

/*Construct Binary Tree from Given Array*/
    public TreeNode buildBinaryTree(char[] treeArray, int index) { //The treeArray is supposed to be the levelorder array of a tree, 'X' is used for representing null
        if (treeArray == null || treeArray.length == 0) {
            return null;
        }

        if (index < treeArray.length) {
            char value = treeArray[index];
            if (value != 'X') {
                int valueInt = Integer.parseInt(String.valueOf(value));
                System.out.println(valueInt);
                TreeNode node = new TreeNode(valueInt);
                treeArray[index] = 'X';
                node.left = buildBinaryTree(treeArray, index * 2);
                node.right = buildBinaryTree(treeArray, index * 2 + 1);
                return node;
            }
        }
        return null;
    }

/*
Binary Tree Preorder Traversal  
Given a binary tree, return the preorder traversal of its nodes' values. 
    Example 
    Given:
        1
       / \
      2   3
     / \
    4   5
    return [1,2,4,5,3].

Challenge Can you do it without recursion?
Tags Recursion Binary Tree Binary Tree Traversal Non Recursion 
*/

//Version 0: Non-Recursion (Recommend)
    public List<Integer> preorderTraversalOne() {

    	ArrayDeque<TreeNode> stack = new ArrayDeque<TreeNode>();
    	List<Integer> preorder = new ArrayList<Integer>();

    	if (root == null) {
    		return preorder; // This is NOT the termination for recursion. 
    	}

    	stack.add(root);
    	
    	while (!stack.isEmpty()) {
    		TreeNode node = stack.pop();
    		preorder.add(node.val);
    		System.out.print(node.val + " ");
    		if (node.right != null) {
    			stack.push(node.right); 
    		}
    		if (node.left!= null) {
    			stack.push(node.left); // FILO, so need to push left at last
    		}
    	}
    	System.out.println("\n");
    	return preorder;
    }

    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> inorder = new ArrayList<Integer>();
        ArrayDeque<TreeNode> stack = new ArrayDeque<TreeNode>();
        
        if (root == null) {
            return inorder;
        }
        
        TreeNode cur = New TreeNode();
        
    }



/**   
     *                 180  
     *                 /  \  
     *               65    5  
     *              /  \    \  
     *             97  25   37  
     *            /      \    \ 
     *           22      28    32
     */  

    public static void main (String[] args) {
        char[] arr = {'X','180','65','5','97','25','X','37','22','X','X','28','X','X','X','32'};
        /*char[] arr = {'X','180','65','5','97','25','25','37'};*/
        BinaryTreeLintcode test = new BinaryTreeLintcode(arr);
        TreeNode testRoot = test.root;
        test.preorderTraversalOne();
    }

}