Given preorder array construct a BST

Question

Ok, code reviewers, I want you to pick my code apart and give me some feedback on how I could make it better or more simple. Also its really hard to make this code work if preorder array contains duplicate. Any code/psuedocode is useful.

public class PreOrderTraversalBST {

    private TreeNode root;

    private static class TreeNode {
        TreeNode left;
        int item;
        TreeNode right;

        TreeNode (TreeNode left, int item, TreeNode right) {
            this.left = left;
            this.item = item;
            this.right = right;
        }
    }

    /**
     * QQ: is there any alternative for this ?
     */
    private static class Counter {
        int counter;

        Counter(int counter) {
            this.counter = counter;
        }

    }

    public void preOrderRecursive (int[] a) {
        root = dpPreOrderRecursive (a, new Counter(0), Integer.MIN_VALUE, Integer.MAX_VALUE );
    }


    private TreeNode dpPreOrderRecursive (int[] arr, Counter counter, int min, int max) {

        if (counter.counter < arr.length && arr[counter.counter] > min && arr[counter.counter] < max) {

            int item = arr[counter.counter];

            TreeNode treeNode = new TreeNode(null, item, null);

            counter.counter++;
            treeNode.left = dpPreOrderRecursive(arr, counter, min, item);
            treeNode.right = dpPreOrderRecursive(arr, counter, item, max);

            return treeNode;
        }
        return null;
    }


    public void preOrderWithStack (int[] arr) {

       final Stack<TreeNode> stack = new Stack<TreeNode>();
       root = new TreeNode(null, arr[0], null);
       stack.push(root);
       int i = 1;

       while (arr[i] < root.item) {
           TreeNode node = new TreeNode(null, arr[i], null);
           if (arr[i] < stack.peek().item) {
               stack.peek().left = node;
           } else {
               TreeNode temp = null;
               while (!stack.isEmpty() && arr[i] >= stack.peek().item) {
                   temp = stack.pop();
               }
               temp.right = node;
               stack.push(temp);
           }
           stack.push(node);
           i++;
       }

       TreeNode rightNode = new TreeNode(null, arr[i], null);
       root.right = rightNode;
       stack.push(rightNode);
       i++;

       while (i < arr.length) {
           TreeNode node = new TreeNode(null, arr[i], null);
           if (arr[i] >= stack.peek().item) {
               stack.peek().right = node;
               stack.push(node);
           } else {
               TreeNode temp = null;
               while (!stack.isEmpty() && arr[i] < stack.peek().item) {
                   temp = stack.pop();
               }
               temp.left = node;
               stack.push(temp);
           }
           stack.push(node);
           i++;
          }
        }
}

Complexity check. Does stack based solution account to O(nlogn) time comlexity or O(n2) ?

Answer 1

Your binary tree setup does not appear to be well balanced.... and no, the counter is unnecessary. I think you have perhaps over-thought the process...

If the data is pre-sorted, you can simply bifurcate your data in a recursive process.

Your method is very close to what I would do, so copy/paste:

private TreeNode dpPreOrderRecursive (int[] arr, /*Counter counter,*/ int min, int max) {

    int mid = (min + max) >> 1;
    TreeNode treeNode = new TreeNode(null, arr[mid], null);
    treeNode.left = mid > min ? dpPreOrderRecursive(arr, min, mid - 1) : null;
    treeNode.right = mid + 1 < max ? dpPreOrderRecursive(arr, mid + 1, max) : null;
}

Then, you can get your tree with:

TreeNode root = dpPreOrderRecursive(arr, 0, arr.length);

(none of the Integer.MIN/MAX).