CareerCup

Revision and simplified version:

public class CartesianTree {
	
	public static class Node {
		public int value;
		public Node left;
		public Node right;
	}
	
	public static Node build(int[] data) {
		if (data == null || data.length == 0) return null;
		return build(data, 0, data.length - 1);
	}
	
	private static Node build(int[] data, int start, int end) {
		if (end < start) return null;
		int min = Integer.MAX_VALUE;
		int minIndex = -1;
		
		for (int i = start; i <= end; i++) {
			if (data[i] < min) {
				min = data[i];
				minIndex = i;
			}
		}
		
		Node node = new Node();
		node.value = min;
		
		node.left = build(data, start, minIndex - 1);
		node.right = build(data, minIndex + 1, end);
		
		return node;
	} 
}

Both of you are right; Pseudo Code of constructing cartesian tree from sequence of nodes:
1.Find the lowest number in the sequence suppose A[1..N] is the sequnce of numbers and A[i] is the lowest.
2. Make this A[i] root of the tree.
3. Devide whole tree into two part A[1..i-1] and A[i+1..N]
4. Apply step 1 to 3 on these two subtrees.

public class CartesianTree {
	
	public static class Node {
		public int value;
		public Node left;
		public Node right;
	}
	
	public static Node build(int[] data) {
		if (data == null || data.length == 0) return null;
		return build(data, 0, data.length - 1, null, false);
	}
	
	private static Node build(int[] data, int start, int end, Node parent, boolean fromLeft) {
		if (end < start) return null;
		int min = Integer.MAX_VALUE;
		int minIndex = -1;
		
		for (int i = start; i <= end; i++) {
			if (data[i] < min) {
				min = data[i];
				minIndex = i;
			}
		}
		
		Node node = new Node();
		node.value = min;
		
		if (parent != null) {
			if (fromLeft) parent.left = node;
			else parent.right = node;
		}
		
		node.left = build(data, start, minIndex - 1, node, true);
		node.right = build(data, minIndex + 1, end, node, false);
		
		return node;
	} 
}


}

There is a O(n) solution to this problem. Yours is not O(n)

public TreeNode build(int[] a)
        {
                TreeNode root = null;
                Stack<TreeNode> stack = new Stack<TreeNode>();
                for(int i = 0; i < a.length; i++) {
                        TreeNode last = null;
                        while(!stack.empty() && stack.peek().val > a[i]) last = stack.pop();
                        TreeNode node = new TreeNode(a[i]);
                        node.left = last;
                        if(stack.empty()) root = node;
                        else stack.peek().right = node;
                        stack.push(node);
                }
                return root;
        }

// following is the O(N) time algorithm for constructing Cartesian tree from in-order traversal of the binary search tree (i.e. sorted sequence).

Please suggest improvement

static Node cTree(int[] a, int start, int end) {
		
		// let's construct 1...
		// for the remaining array...
		// construct the left child... 2n + 1
		// construct the right child...2n + 2.
		if (start > end)
			return null;
		
		int key = a[start];
		Node n = new Node(key);
		n.left = cTree(a, 2*start + 1, end);
		n.right = cTree(a, 2*start + 2, end);
		
		return n;
	}

It is never said that it is a BST....