Binary tree searching

Replies

• 

  Kaustubh Katdare

  rama_krish627

  Hi can any one give me code for searching a key node in a binary tree.
  (code is either in java or c++ better in java)😛

  Friend, you want everything ready made? How about sharing your efforts with us? We'd love to help you with the problems you are facing while writing the code than providing you with all the code ready made.
  
  What do you say?
• 

  Ashutosh_shukla

  Ya you tell what you tried at least your logic then we will try to correct it if you want it i have it ready but in PASCAL!!!!!!!!!!!!!
  You take up a good book on data structures and you will get the algorithm.
  If you understand it you can easily do the coding.
  Remember you can implement the tree using the linked list.
  See if this helps.
• 

  rama_krish627

  The function calling here is
  List2 ptr=search_link(root,key);
  /*here lc is left child and rc is right child*/
  
  List2 search_link(List2 root,String key1)
  {
  if(!((root.data).equals(key1)))
  {
  
  if(root.lc!=null)
  {
  System.out.println(" lc entered");
  return(search_link(root.lc,key1));
  }
  else
  {
  return(null);
  }
  if(root.rc!=null)
  {
  System.out.println("rc entered");
  return(search_link(root.rc,key1));
  }
  else
  {
  return(null);
  }
  }
  else
  {
  System.out.println("key found");
  return(root);
  }
  return(null);
  }
  
  what is the problem with this can you help me.
• 

  shalini_goel14

  Hi rama_krish,
  
  I feel the problem in above code is using following logic:
  
  if(root.lc!=null)
  call function again
  else
  return null
  
  Here you should check right sub tree,instead of returning null, so every time after function do not find any item in left sub tree,it returns null without checking in right subtree.
  
  Why don't you try something like below:
  

  /*
   * BinaryTreeSearch.java
   *
   * Created on December 26, 2008, 1:41 PM
   *
   * To change this template, choose Tools | Template Manager
   * and open the template in the editor.
   */
  package myjava;
  /**
   *
   * @author shalinig
   */
  public class BinaryTreeSearch {
      
      /** Creates a new instance of BinaryTreeSearch */
      public BinaryTreeSearch() {
      }
      
      public static void main(String[] args) {
          //Add your code for creating abinary tree.
          
          //call searchInTree( BinaryTreeNode node, String item ) for searching
      }
      
      
      static boolean searchInTree( BinaryTreeNode node, String item ) {
          // Return true if item is one of the items in the binary
          // sort tree to which node points.   Return false if not.
          if ( node == null ) {
              // Tree is empty, so it certainly doesn't contain item.
              return false;
          } else if ( item.equals(node.item) ) {
              // Yes, the item has been found in the root node.
              return true;
          } else if ( item.compareTo(node.item) < 0 ) {
              // If the item occurs, it must be in the left subtree.
              // So, return the result of searching the left subtree.
              return searchInTree( node.left, item );
          } else {
              // If the item occurs, it must be in the right subtree.
              // So, return the result of searching the right subtree.
              return searchInTree( node.right, item );
          }
      }  // end treeContains()
      
      
      
      class BinaryTreeNode {
          // An object of type BinaryTreeNode represents one node
          // in a binary tree of strings.
          String item;      // The data in this node.
          BinaryTreeNode left;    // Pointer to left subtree.
          BinaryTreeNode right;   // Pointer to right subtree.
          BinaryTreeNode(String str) {
              // Constructor.  Make a node containing str.
              item = str;
          }
      }  // end class BinaryTreeNode
      
  }
  
  

  Hope this may be of some help !! 😀
• 

  rama_krish627

  shalini_goel14

  Hi rama_krish,
  
  I feel the problem in above code is using following logic:
  
  if(root.lc!=null)
  call function again
  else
  return null
  
  Here you should check right sub tree,instead of returning null, so every time after function do not find any item in left sub tree,it returns null without checking in right subtree.
  
  Why don't you try something like below:
  

  /*
   * BinaryTreeSearch.java
   *
   * Created on December 26, 2008, 1:41 PM
   *
   * To change this template, choose Tools | Template Manager
   * and open the template in the editor.
   */
  package myjava;
  /**
   *
   * @author shalinig
   */
  public class BinaryTreeSearch {
      
      /** Creates a new instance of BinaryTreeSearch */
      public BinaryTreeSearch() {
      }
      
      public static void main(String[] args) {
          //Add your code for creating abinary tree.
          
          //call searchInTree( BinaryTreeNode node, String item ) for searching
      }
      
      
      static boolean searchInTree( BinaryTreeNode node, String item ) {
          // Return true if item is one of the items in the binary
          // sort tree to which node points.   Return false if not.
          if ( node == null ) {
              // Tree is empty, so it certainly doesn't contain item.
              return false;
          } else if ( item.equals(node.item) ) {
              // Yes, the item has been found in the root node.
              return true;
          } else if ( item.compareTo(node.item) < 0 ) {
              // If the item occurs, it must be in the left subtree.
              // So, return the result of searching the left subtree.
              return searchInTree( node.left, item );
          } else {
              // If the item occurs, it must be in the right subtree.
              // So, return the result of searching the right subtree.
              return searchInTree( node.right, item );
          }
      }  // end treeContains()
      
      
      
      class BinaryTreeNode {
          // An object of type BinaryTreeNode represents one node
          // in a binary tree of strings.
          String item;      // The data in this node.
          BinaryTreeNode left;    // Pointer to left subtree.
          BinaryTreeNode right;   // Pointer to right subtree.
          BinaryTreeNode(String str) {
              // Constructor.  Make a node containing str.
              item = str;
          }
      }  // end class BinaryTreeNode
      
  }
  
  

  Hope this may be of some help !! 😀

  Hi Shalini. I think this code work for the Binary Search tree why because you compared the items in the tree whether they are less than or greater than a particular node.
  but my requirement is searching for a given key node and it has to return the reference or address so that I can delete or insert some other node.
• 

  Ashutosh_shukla

  How about using recursion???????
  I guess you can use recursion easily with the trees.
  Call a function that returns the address of the node.
  Inside the function check if the passed reference is null then return null else you will check for the node itself and then if node matches return its reference.
  Now if node is not the required one call the function for its left child and if on searching the left sub tree you don't get it then go for right sub tree.
  Algorithm can be expressed as follows:
  [Algorithm]
  Passed parameter : node *n,string key
  Returned type : node*
  The body is :
  Create local node *t
  if(n==NULL)
  t = NULL;
  else
  {
  if(n.data==key)
  t = n;
  else
  {
  t=function(n->left,key);
  if(t==NULL)
  t=function(n->right,key);
  }
  }
  return t;
  Call the function in your main routine and check whether it returned the NULL or some meaningful reference.
  Now you got most of it i guess.
  👍
• 

  nileshchakkar

  k lastly try this is best bz created me .. so must try this..
  everyone try 2 xplain u code i will xplain u logic
  consider a tree first of all suppose u hv a binary search tree
  
  
  assume u create a BST before then
  

  bt* delnode(bt *t)
  {
      bt *ptr,*prev,*temp;
      int n;
      ptr=t;
  
      printf("\nENTER THE NODE TO BE DELETED : ");
      scanf("%d",&n);
  
      while(ptr!=NULL && ptr->data!=n)
      {
          prev=ptr;
          if(ndata)
              ptr=ptr->lc;
          else
              ptr=ptr->rc;
      }
  
      if(ptr->data!=n)
      {
          printf("\nNODE NOT FOUND ");
      return(t);
      }
  
  
       if(ptr->lc==NULL && ptr->rc==NULL)
       {
        if(ndata)
          prev->lc=NULL;
        else
          prev->rc=NULL;
       }
  
       else
  
       if(ptr->lc==NULL && ptr->rc!=NULL)
       {
        if(ndata)
          prev->lc=ptr->rc;
        else
          prev->rc=ptr->rc;
       }
  
       else
  
       if(ptr->lc!=NULL && ptr->rc==NULL)
       {
        if(ndata)
          prev->lc=ptr->lc;
        else
          prev->rc=ptr->lc;
       }
  
       else
  
       {
          temp=ptr->rc;
  
          while(temp->lc!=NULL)
               temp=temp->lc;
               temp->lc=ptr->lc;
  
          if(ptr==t)
              t=ptr->rc;
          else
          {
           if(ndata)
              prev->lc=ptr->rc;
           else
              prev->rc=ptr->rc;
          }
       }
       free(ptr);
  
          return(t);
  }
    */
  
  bt* delNode(bt* root)
  {
      bt*p,*q,*f,*rp,*s;
  
      int data;
  
      printf("\nEnter data to be search");
      scanf("%d",&data);
  
  
  
      p=root;
      q=NULL;
  
      while(p!=NULL && p->data!=data)
      {
         q=p;
  
         if(datadata)
       p=p->lc;
         else
       p=p->rc;
      }
  
      if(p==NULL)
      {
         printf("\nData not Present in Tree...");
         return root;
      }
  
      if(p->lc==NULL)
       rp=p->rc;
  
      if(p->rc==NULL)
        rp=p->lc;
  
       if(p->lc  && p->rc)
       {
        f=p;
        rp=p->rc;
        s=rp->lc;
  
        while(s)
        {
            f=rp;
            rp=s;
            s=s->lc;
        }
  
        if(f!=p)
        {
            f->lc=rp->rc;
            rp->rc=p->rc;
        }
  
            rp->lc=p->lc;
     }
     if(q==NULL)
        root=rp;
     else
     {
      if(p==q->lc)
         q->lc=rp;
      else
         q->rc=rp;
     }
     return root;
  }

• 

  Ashutosh_shukla

  I guess you posted code and explained nothing and i told mechanism using recursion and not code
• 

  ideamonk

  try this code in C++
  #-Link-Snipped-#
  
  edit it to suit your needs. Have fun 😀