After adding an elements to the Bst its only saves last 3 elements when i try to search an element it only search in the last 3 elements

I'am trying to add elements to my Bst and it added all the elements i ask to added but when i try to search in elements its always search in the last 3 elements in my code there is an add function that i call for inserting the elements and for searching iam using contains function that return true or false if the element is found ... after adding some elements , i tried to search for element in the first 3 elements and in the last 3 elements it finds it but when i search in more than 3 elements its only check in the last 3 , i tried to debug then i saw its only check in the last 3 elements that added, even when i try to add element that is already in the tree , if the element in the last 3 elements it return false but if its not it return true like , again checks only in the last 3 elements my code:

code:

public class BinarySearchTree<T extends Comparable<T>> {

    BstNode root;
    private int sizeoftree=0;

    // Binary Search Tree Node
    class BstNode {
        T val;
        BstNode left, right;

        public BstNode(T val) {
            this.val = val;
            left = null;
            right = null;
        }
    }




public BinarySearchTree() {
        this.root=null;
    }

    public int size(){
        return sizeoftree;
    }



public boolean add(T val) {         
         if (this.root == null) {
                this.root=new BstNode(val);
                sizeoftree  ;
                return true;
            }
            while (this.root != null)
            {
                if (val.compareTo(this.root.val) < 0) {
                    if(this.root.left==null)
                    {
                        this.root.left=new BstNode(val);
                        sizeoftree  ;
                        return true;
                    }
                    this.root = this.root.left;
                }
                else if(val.compareTo(this.root.val) > 0) {
                    if(this.root.right==null)
                    {
                        this.root.right=new BstNode(val);
                        sizeoftree  ;
                        return true;
                    }
                    this.root = this.root.right;
                }
                if(val.compareTo(this.root.val)==0)
                {
                    return false;
                }
            }
            
            return false;
    }
    


public boolean contains(T val) 
    {
        return search(this.root, val);
    }
    
     
     private boolean search(BstNode root, T data) {
            if (root == null) {
                return false;
            } else if (root.val.compareTo(data)==0) {
                return true;
            } else if (root.val.compareTo(data) > 0) {
                return search(root.left, data);
            }
                 return search(root.right, data);
            
        }





public static void main(String[] args)
{
    BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
    tree.add(5);
    tree.add(4);
    tree.add(2);
    tree.add(3);
    tree.add(6);
    tree.add(1);
    tree.contains(5);
    }
}

CodePudding user response：

The problem is that you change the root of the tree, and misuse it for navigating down the tree, thereby losing the reference to what should remain the actual root of the tree. The only time the add method should assign to this.root is when the tree is empty:

 this.root=new BstNode(val);

All other times you have an assignment to this.root, it is wrong.

So instead of statements like this:

this.root = this.root.left;

...you should use a local variable (let's say current), which you should initialise as

BstNode current = this.root;

...and which you should then use for navigating through the tree with statements like:

current = current.left;

Once you understand this issue, you should be able to update your code consistently.