CODEWITHSUNDEEP
algorithmbinary-search-tree
IUnknown
IUnknown

Reputation: 9839

BST traversal pre-order

In a BST pre-order traversal,I do not see the result I would have expected.
Please help confirm whether it is an issue with the code or my understanding of how pre-order traversal would work.

Node:

class node implements Comparable<node>{
        int v;
        node left;
        node right;
        node(int v){ this.v=v;}
        boolean equals(node o){
            return(this.v==o.v);
        }
        @Override public int compareTo(node aThat) {
            return this.v<aThat.v?-1:this.v>aThat.v?1:0;
        }
        public String toString(){ return "->" + this.v;}
    }

Insertion code - 

public binarySearch(int r){
        Random rnd=new Random();
        int[] val=new int[r];
        for(int i=0;i<r;i++){
            val[i]=rnd.nextInt(50);
        }
        System.out.println("Array -> " + Arrays.toString(val));
        root=new node(val[0]);
        for(int i=1;i<val.length-1;i++){
            insert(root,new node(val[i]));
        }
    }

Insertion(build-up) code - 

private void insert(node curr,node c){
    if(curr==c){ return;}
    if(curr.compareTo(c)<0)
    {
        if(curr.left==null){curr.left=c; return;}
        insert(curr.left,c);
    }
    else
    {
        if(curr.right==null){curr.right=c; return;}
        insert(curr.right,c);
    }
}

Traversal code (pre-order)- 

private void print(node c){
        if(c==null) return;
        System.out.println(c);
        print(c.left);
        print(c.right);

    }

Input array - 

 [22, 17, 24, 11, 5, 9, 25]

Expected(?) - 

 ->22 ->17 ->11 ->5 ->9 ->24

Output - 

 ->22 ->24 ->17 ->11 ->5 ->9

Upvotes: 0

Views: 85

Answers (1)

ruakh
ruakh

Reputation: 183602

You are using curr.compareTo(c)<0 (meaning "c is greater than curr") as the condition for putting c on the left of curr. I'm not sure exactly what you meant to write, but it would be the exact opposite of this. (Either flip c and curr, or change < to >, or swap left and right.)

Upvotes: 1

Related Questions