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

You should be calling printPreOrderrecursively. You are calling printInorder instead, so your calls are not recursive. — meghamind
– meghamind, Commented Nov 12, 2013 at 22:33
@meghamind: my calls are recursive. the input array is given in preOrder and the output I print (both inOrder and PreOrder) should match my input PreOrder array — brain storm
– brain storm, Commented Nov 12, 2013 at 22:37

meghamind · Accepted Answer · 2013-11-13 05:41:32Z

2

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

edited Nov 13, 2013 at 5:41

answered Nov 12, 2013 at 22:37

meghamind

964 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

brain storm Over a year ago

please see my updated code..I forgot to paste method for PrintPreOrder previously. also look at my comment above

meghamind Over a year ago

I was referring to the printPreOrder method posted. It doesn't seem to be calling itself recursively - instead it calls printInorder(root.left);

brain storm Over a year ago

Thank you, I got what you mean..you are correct..fixing this works now..stupid me..

Trying · Accepted Answer · 2013-11-12 22:42:19Z

1

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

answered Nov 12, 2013 at 22:42

Trying

14.3k11 gold badges72 silver badges113 bronze badges

2 Comments

brain storm Over a year ago

Thanks for the solution. I have implemented using recursion. but I wanted to get the stack method working as cited by many people in the link I provided. may be I should stick with recursion..what is the complexity here. It is O(n) correct..

brain storm Over a year ago

Thanks, As pointed by the answer below, I messed up my recursive call for printing, fixing it makes it work now..

Collectives™ on Stack Overflow

implementing binary Search tree reconstruction from preOrder array in Java?

2 Answers 2

3 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related