CareerCup

static class Node {
		Node(int data) {
			this.data = data;
		}

		@Override
		public String toString() {
			return this.data + " ";
		}

		int data;
		Node left;
		Node right;
		Node next;
	}
	
	public static void main(String args[]) throws Exception {
		int arr[] = { 4, 2, 1, 3, 6, 5, 7 };
		Node root = builtTreeFromPreOrder(arr);
		System.out.println(root);
	}

	public static Node builtTreeFromPreOrder(int arr[]) {
		Stack<Node> stack = new Stack<Node>();
		Node root = new Node(arr[0]);
		stack.push(root);
		int index = 1;
		while (index < arr.length) {
			if (!stack.isEmpty() && stack.peek().data > arr[index]) {
				Node temp = new Node(arr[index]);
				stack.peek().left=temp;
				stack.push(temp);
				index++;
			} else {
				Node temp = null;
				while (!stack.isEmpty() && stack.peek().data < arr[index]) {
					temp = stack.pop();
				}
				if (temp != null) {
					Node temp1 = new Node(arr[index]);
					temp.right = temp1;
					stack.push(temp1);
					index++;
				}
			}
		}
		return root;
	}

Psuedocode:
int index = 0;
function(A, min, max):
node = null;
if(A[index] between min and mx)
node= A[index]
index++
node.left = function(A, min,A[index])
node.right = function(A, A[index], max)

return node;

// Time Complexity O(n)
static Node constructTree(int[] pre, int size) {

                Node root = new Node(pre[0]);
                Stack<Node> stack = new Stack<Node>();

                stack.push(root);

                for (int index = 1; index < size; index++) {

                        Node temp = null;

                        while (!stack.isEmpty() && pre[index] > stack.peek().data) {
                                temp = stack.pop();
                        }

                        if (null != temp) {
                                temp.right = new Node(pre[index]);
                                stack.push(temp.right);
                        } else {
                                temp = stack.peek();
                                temp.left = new Node(pre[index]);
                                stack.push(temp.left);
                        }
                }

                return root;
        }

// Time Complexity O(n)
static Node constructTree(int[] pre, int size) {

                Node root = new Node(pre[0]);
                Stack<Node> stack = new Stack<Node>();

                stack.push(root);

                for (int index = 1; index < size; index++) {

                        Node temp = null;

                        while (!stack.isEmpty() && pre[index] > stack.peek().data) {
                                temp = stack.pop();
                        }

                        if (null != temp) {
                                temp.right = new Node(pre[index]);
                                stack.push(temp.right);
                        } else {
                                temp = stack.peek();
                                temp.left = new Node(pre[index]);
                                stack.push(temp.left);
                        }
                }

                return root;
        }

public static TreeNode getTreeFromPreorder(int[] nums){
        Deque<TreeNode> deque = new ArrayDeque<>();
        if(nums==null || nums.length<1){
            return null;
        }
        
        TreeNode root = new TreeNode(nums[0]);
        deque.offer(root);
        for(int i=1;i<nums.length;i++){
            TreeNode node = new TreeNode(nums[i]);
            TreeNode temp = null;
            while(!deque.isEmpty()&&deque.peekLast().val<node.val){
                temp = deque.pollLast();
            }
            if(temp!=null){
                temp.right = node;
                deque.offer(node);
            }else{
                deque.peekLast().left = node;
                deque.offer(node);
            }
            
        }
        return root;
    }

public static TreeNode getTreeFromPreorder(int[] nums){
        Deque<TreeNode> deque = new ArrayDeque<>();
        if(nums==null || nums.length<1){
            return null;
        }
        
        TreeNode root = new TreeNode(nums[0]);
        deque.offer(root);
        for(int i=1;i<nums.length;i++){
            TreeNode node = new TreeNode(nums[i]);
            TreeNode temp = null;
            while(!deque.isEmpty()&&deque.peekLast().val<node.val){
                temp = deque.pollLast();
            }
            if(temp!=null){
                temp.right = node;
                deque.offer(node);
            }else{
                deque.peekLast().left = node;
                deque.offer(node);
            }
            
        }
        return root;
    }