CODEWITHSUNDEEP
javarecursion
Layla
Layla

Reputation: 5446

adding recursively an item into a binary tree

I am implementing a binary tree in Java like the following:

public class Node {
    int item;
    Node left;
    Node right;
    public Node (int n){
        item=n;
        left=null;
        right=null;
    }
    public int getItem(){
        return item;
    }
}

public class Tree{
         Node root;
  public void add(int item){
        if (root==null){
            root=new Node(item);
        }
        else{
            Node rootT;
            rootT=root;
            rooT=add(rooT,item);
        }
    }
    public Node add(Node n, int item){
        if (n==null){
            n=new Node(item);
        }
        else{
            if (item<root.item){
                n.izq=add(n.left,item);
            }
            else{
                n.right=add(n.right,item);
            }
        }
        return n;
    }
    public void inorder(Node n){
        if (n!=null){
            inorder(n.left);
            System.out.println(n.item);
            inorder(n.right);
        }
    }  
}

I am using rootT to traverse the tree without changing the value of the original tree. The problem that I have is that when I add the elements [10,100,20,5,4], it prints me 4,5,10,100,20; which is not the correct order, what is wrong? Thanks

Upvotes: 0

Views: 195

Answers (1)

Maxaon3000
Maxaon3000

Reputation: 1129

Your code has a bug in it:

public Node add(Node n, int item){
    if (n==null){
        n=new Node(item);
    }
    else{
        if (n<root.item){
            n.izq=add(n.left,item);
        }
        else{
            n.right=add(n.right,item);
        }
    }
    return n;
}

You're always comparing to the root of the tree (it shouldn't even compile since you're comparing the node to an integer). Whereas you should be comparing to the current node in the recursion:

public Node add(Node n, int item){
    if (n==null){
        n=new Node(item);
    }
    else{
        if (item<n.item){
            n.izq=add(n.left,item);
        }
        else{
            n.right=add(n.right,item);
        }
    }
    return n;
}

Upvotes: 1

Related Questions