implementing binary Search tree reconstruction from preOrder array in Java?

Question

I have followed this idea and this C++ code to reconstruct binary Search Tree from PreOrder array in Java. I am not reinventing the algorithm, but trying to implement pseudocode. I need help here. I do not get the correct output. The output I get is below the code.

public class BinaryTreeMethods {           
        public static void main(String[] args) {

        int[] arr = {7,5,3,6,9,8,10};
        Node newone = CreateFromPreOrder(arr,arr.length);
            printInorder(newone);
            System.out.println();
            printPreOrder(newone);

public static Node CreateFromPreOrder(int[] arr, int length) {

            if(length==0)
               return null;
            Node root = new Node(arr[0]);
            Stack<Node> s = new Stack<Node>();
            s.push(root);
            for(int i=1; i<length; i++)
            {

            Node tmp = new Node(arr[i]);
            Node next = s.peek();
            if(tmp.data < next.data)
            {
            next.left = tmp;
            }
            else
            {
            Node popped = null;
            while(!s.isEmpty() && tmp.data > next.data)
            {
            popped= s.peek();
            s.pop();
            }
            popped.right = tmp;
            }
            s.push(tmp);
            }
            return root;
            }
     public static void printInorder(Node root) {

            if (root!=null){
                printInorder(root.left);
                System.out.print(" " + root.data);
                printInorder(root.right);
            }
        }

class Node {
    Node left;
    Node right;
    int data;

    public Node(int c){
        this(c, null, null);
    }
    public Node(int c,Node left, Node right) {
        this.data = c;
        this.left=left;
        this.right=right;
    }


}




     public static void printInorder(Node root) {

            if (root!=null){
                printInorder(root.left);
                System.out.print(" " + root.data);
                printInorder(root.right);
            }
        }


public static void printPreOrder(Node root) {

            if (root!=null){
                System.out.print(" " + root.data);
                printInorder(root.left);
                printInorder(root.right);
            }
        }
            } 

I do not get the expected output:

3 5 7 6 8 9 10
 7 3 5 6 8 9 10

Answer 1

Looks like the recursive printing is messed up. Here printPreOrder should be calling itself to traverse left and right subtrees than calling printInOrder to do the traversal.

public static void printPreOrder(Node root) {

            if (root!=null){
                System.out.print(" " + root.data);
                printPreOrder(root.left); 
                printPreOrder(root.right);
            }
        }
    }     

Answer 2

Using explicit stack is like over complicating the code, so would rather go with recursion which is pretty easy to grasp. Just recessively calculate the min, max and the index which is indicating the current pointer in the array.

TreeNode createTree(int[] a, Index i, int min, int max) {
    if (i.index >= a.length) {
        return null;
    }
    if (a[i.index] > min && a[i.index] < max) {
        int current = a[i.index];
        TreeNode t = new TreeNode(a[i.index]);
        i.index = i.index + 1;
        t.left = createTree(a, i, min, current);
        t.right = createTree(a, i, current, max);
        return t;
    }
   return null;
}

where Index class is given below:

class Index {

    int index;

    Index(int k) {
        index = k;
    }
}