Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am having a confusion in this Binary Tree Coding. I know the concept of binary tree and I know how those work and all, but in this source code i am confused with "Find" operation. I cannot understand how it works and all. Please help me, I am so interested in this area.

package binarytree_task4;


  class Node 
    {

    private static class Equivalent {

        public Equivalent() {
        }
    }

        public Equivalent data; 
        public Node right; 
        public Node left; 

        public Node(Equivalent data) 
        {

            this(data, null, null);
        }

        public Node(Equivalent data, Node left, Node right) 
        {

            this.data = data;
            this.left = left;
            this.right = right;
        }   
    }


 class binarytree {


    public static void main(String[] args) {

    }

    private static class Equivalent {

        public Equivalent() {
        }
    }

    private static class present {

        public present() {
        }
    }
    private Node root; 
    private int size;

    public binarytree() 
    {
        size = 0;
        root = null;
    }


    public void printTree() 
    {
        if(size == 0)
            System.out.println("Empty");
        else {
            System.out.println("Tree contents:");   
            inorder(root);
        }
    }


    public void inorder(Node present)
    {
        if(present != null) 
        {
            inorder(present.left);
            System.out.println(present.data);
            inorder(present.right);
        }
    }  

    public void Insert(Equivalent data) 
    {
        root = Insert(data, root);
    }


    private Node Insert(Equivalent data, Node present) 
    {
        if( present == null) 
        {
            size++; 
            present = new Node(data, null, null); 
        }

        else if(data.compareTo(present.data)<0)
        {
            present.left = Insert(data,present.left);
                }

        else if(data.compareTo(present.data)>0)
                { 

            present.right = Insert(data, present.right);
        }

        return present;
    }  



    public boolean Find(Equivalent data) 
    {
        return Find(data, root);    
    }


    private boolean Find(Equivalent data, Node present) 
    {

        if(present == null ) 
        {
            return false;
        }
        else if(present.data == data)
        {
            return true;    
        }
        else if(data.compareTo(present.data)<0)  
        {
            return Find(data, present.left); 
        }
        else 
        {
            return Find(data, present.right); 
        }
    }



    public boolean Delete(Equivalent key){

        if (Find(key)){
            Delete(key);
            return true;
        }
        else{
            return false;
        }
    }

    public void delete(Equivalent key) 
    { 
        Node present = root;
        Node parent = root;

        boolean isLeftChild = true;


        while(present.data.compareTo(key) != 0)        
        {

            parent = present;
            if(present.data.compareTo(key) > 0)      
            {
                isLeftChild = true; 
                present = present.left; 
            }
            else                            
            {
                isLeftChild = false; 
                present = present.right; 
            }
            if(present == null)            
                return ;            
        }   

        if(present.left == null && present.right == null) 
        {
            if(present == root) 
                root = null;                
            else if(isLeftChild)      
                parent.left = null;    
            else                             
                parent.right = null;
        }

        else if(present.right == null)   
            if(present == root)      
                root = present.left; 
            else if(isLeftChild) 
                parent.left = present.left;  
            else 
                parent.right = present.left;  

        else if(present.left == null)    
            if(present == root)              
                root = present.right;    
            else if(isLeftChild) 
                parent.left = present.right; 
            else  
                parent.right = present.right;   

        else 
        {

            Node successor = getSuccessor(present); 

            if(present == root)  
                root = successor;
            else if(isLeftChild)     
                parent.left= successor; 
            else
                parent.right = successor;

            successor.left = present.left; 
         }   
    }


   private Node getSuccessor(Node delNode)
   {
        Node successorParent = delNode;  
        Node successor = delNode;    
        Node present = delNode.right; 

        while(present != null) 
        { 


            successorParent = successor; 
            successor = present;             
            present = present.left;          
        }
        if(successor != delNode.right) 
        { 

            successorParent.left = successor.right;  
            successor.right = delNode.right;         
        }
        return successor; 
   }


}
share|improve this question
    
Could you explain your confusion with an example? Find is recursive. Do you understand how recursion works? Also: Which Find function confuses you? You have two, the name is overloaded with to different signatures. –  FrustratedWithFormsDesigner Dec 30 '11 at 15:03
    
Frankly if i tell u the problem is for me, "Equivalent" is an object but how it works in Find method? (I meant in second method) –  Reem Dec 30 '11 at 15:10
1  
did you try to compile this code? did compilation pass at statement present = new Node(data, null, null);? why there are two classes - Node.Equivalent and binarytree.Equivalent? –  gnat Dec 30 '11 at 15:35
add comment

1 Answer

up vote 5 down vote accepted

Find works recursively, meaning it can call itself. However, it doesn't just call itself with the same arguments, each time it calls itself it is going deeper into the tree. If there were no checks, this could go on forever. However, this recursion has a couple of checks to terminate the search if it is given a null node (meaning, it didn't find what it was looking for), or the node it is given is the one being looked for (meaning it did find the one it was looking for). Eventually one of these conditions must be true.

It works like this:

First it looks at the node it was given. If the node is null, it didn't find what it was looking for and there are no children to search, so it returns false. This is the first termination check, and means "we didn't find it".

If the node is not null, then it checks to see if the node has the requested data. This is the second termination check. If it does, it returns true meaning "we found it".

If it doesn't find the requested data, then it must look either to the left or the right depending on whether the requested data is larger or smaller than the current data.

How does it do this last step? By taking either the left or right node, and starting the whole process over by calling itself with the left or right node of the current node and then returning the result. If the node it is currently on is a leaf node (ie: no left or right branches to follow), then a null node will be sent when it calls itself, and as you can see from earlier in the process, if Find is given a null node it will return false.

So, essentially Find says "am I the node we are looking for?" If the answer is no, it then asks itself "is my left node the one we are looking for?" or "is my right node the one I am looking for?" and it keeps asking itself that question as it goes deeper and deeper into the tree.

Notice that in all cases, Find either returns true, false, or the result of the next call to Find. This means that eventually, some version of Find will return true or false when it gets to the end of the tree, and that true or false will work its way back up the chain -- true (or false) will return to the caller, which returns that value to it's caller, which returns that value to it's caller, ... until you are back to where Find was first called.

share|improve this answer
    
Wow Thank you so much my friend. –  Reem Dec 30 '11 at 15:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.