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);
            }
        }
    }