Inorder Traversal of Cartesian Tree

Given an inorder traversal of a cartesian tree, construct the tree.

Cartesian tree : is a heap ordered binary tree, where the root is greater than all the elements in the subtree.

Note: You may assume that duplicates do not exist in the tree.

Example :

Input : [1 2 3]

Return :   
          3
         /
        2
       /
      1

public class Solution {
    // Naive solution ->
    // We know the root is the highest element in the whole array (O(N))
    // Now for all the subtrees, we will be searching the biggest node
    // Complexity will be O(N*Height) worst case -> (N*N), because we will be doing
    // an overall search of N at every level of the tree

    // Now how can we find the max element in a range ? -> SEGMENT Tree
    // So using segment trees, worst case complexity will be O(NlogN)
    static class SegmentTree {
        // Tree stores max element & it's index
        int tree[][], arr[];

        SegmentTree(int[] arr) {
            this.arr = arr;
            int n = arr.length;
            tree = new int[4 * n][];
            buildTree(0, n - 1, 1);
        }

        public void buildTree(int start, int end, int index) {
            if (start == end) {
                tree[index] = new int[] { arr[start], start };
                return;
            }
            int mid = start + (end - start) / 2;
            buildTree(start, mid, 2 * index);
            buildTree(mid + 1, end, 2 * index + 1);
            if (tree[2 * index][0] > tree[2 * index + 1][0])
                tree[index] = tree[2 * index];
            else
                tree[index] = tree[2 * index + 1];
        }

        public int findMax(int L, int R) {
            int[] ans = query(0, arr.length - 1, 1, L, R);
            return ans[1];
        }

        public int[] query(int start, int end, int index, int L, int R) {
            if (start > R || end < L)
                return new int[] { Integer.MIN_VALUE, -1 };
            else if (start >= L && end <= R)
                return tree[index];
            int mid = start + (end - start) / 2;
            int[] leftMax = query(start, mid, 2 * index, L, R);
            int[] rightMax = query(mid + 1, end, 2 * index + 1, L, R);
            if (leftMax[0] > rightMax[0])
                return leftMax;
            return rightMax;
        }
    }

    SegmentTree segTree;

    public TreeNode buildTree(int[] A) {
        segTree = new SegmentTree(A);
        return helper(A, 0, A.length - 1);
    }

    public TreeNode helper(int[] A, int start, int end) {
        if (start > end)
            return null;
        // O(logN)
        int rootIndex = segTree.findMax(start, end);
        TreeNode root = new TreeNode(A[rootIndex]);
        root.left = helper(A, start, rootIndex - 1);
        root.right = helper(A, rootIndex + 1, end);
        return root;
    }
}