1
\$\begingroup\$

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) ?

\$\endgroup\$
2
\$\begingroup\$

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).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.