Recursively searching a binary tree

This is a discussion on Recursively searching a binary tree within the C Programming forums, part of the General Programming Boards category; I am trying to find a given node (char key[]) in a binary tree and return it to main. My ...

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    6

    Recursively searching a binary tree

    I am trying to find a given node (char key[]) in a binary tree and return it to main. My problem is even after I find the node I can't seem to escape from the recursive method. My logic is obviously wrong, but I was thinking: if I find the node I return it to the previous call, then I check that node before attempting to go(call) left or right, if it is the node I want I return that as well, but it just keeps going like a traversal straight through to the end.

    This is my code:
    PHP Code:
    [code]
    TreeNodePtr Search(TreeNodePtr node,char key[MaxWordSize+1]){
      if (
    node != NULL){ 
         if (
    strcmp(node->data.word,key) == 0) return node;
         
    Search(node->left,key);
         if (
    strcmp(node->data.word,key) == 0)return node;
         
    Search(node->right,key);
          }
    }
    [/
    code
    Any help would be appreciated.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,914
    What happens if node == NULL?

    As for the algorithm: just compare the key with the current node's word. If it is equal, you have a match and can return immediately. If not, use that to decide whether to search in the left subtree or the right subtree, but not both (assuming that this is a binary search tree).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    6

    Re: Recursively searching a binary tree

    Quote Originally Posted by laserlight View Post
    What happens if node == NULL?

    As for the algorithm: just compare the key with the current node's word. If it is equal, you have a match and can return immediately. If not, use that to decide whether to search in the left subtree or the right subtree, but not both (assuming that this is a binary search tree).
    Well from the code there that is what i thought i was doing. Lets say after a left call i find the node. I test, its a match, and i try to return to the previous call. On returning it appears the node i return is not the one that the comparsion sees and the node->right receives. it a different node.
    i had some printf statements monitoring the values as i stepped through. I could see it is wrong but for all apparant reasons the code looks write. lastly its a binary tree, not a binary search tree.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Excuse my ignorance, but isn't a Binary Search tree and a Binary Tree (essentially) the same thing. At least Wikipedia seems to imply that if you are searching in a binary tree (using it's binary tree structure rather than scanning all nodes, that is), then it is a binary search tree:
    http://en.wikipedia.org/wiki/Binary_tree

    You are not returning the result from your recursions, so you "loose" the return value.

    You should also look at the result of strcmp and then decide to go EITHER left or right - not both (right now you are traversing EVERY node in the tree).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    the standard library does offer a void *bsearch function.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by slingerland3g View Post
    the standard library does offer a void *bsearch function.
    But that is not going to search a binary tree - it works on a sorted array.

    http://www.manpagez.com/man/3/bsearch/

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    Understood, matsp, I was hoping that reviewing that code would help enlighten those on binary searches in general either for arrays or within linked lists. "Divide and conquer" to the rescue.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,914
    Quote Originally Posted by matsp
    Excuse my ignorance, but isn't a Binary Search tree and a Binary Tree (essentially) the same thing.
    No, not all binary trees are binary search trees.

    Quote Originally Posted by matsp
    At least Wikipedia seems to imply that if you are searching in a binary tree (using it's binary tree structure rather than scanning all nodes, that is), then it is a binary search tree:
    More like: if it is a binary search tree then you can search it using the properties of a binary search tree. After all, just because you use binary search on an unsorted array does not make the unsorted array sorted.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Laserlight, yes, of course, we can have a binary tree that doesn't contain elements in a sorted order. And just like an array, if the elements in the tree aren't in a sorted order.

    If the keys in this tree aren't ordered in alphabetical order (which is what I understood them to be, when I said "Binary tree == Binary Search Tree"), then you obviously have to visit every node to see if that node matches. It should be sufficient to compare once per node, however.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,668
    > Search(node->left,key);
    Perhaps you should examine the return result of the recursive call.
    If it returns NULL, carry on looking, else....
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by fread View Post
    Well from the code there that is what i thought i was doing. Lets say after a left call i find the node. I test, its a match, and i try to return to the previous call. On returning it appears the node i return is not the one that the comparsion sees and the node->right receives. it a different node.
    i had some printf statements monitoring the values as i stepped through. I could see it is wrong but for all apparant reasons the code looks write. lastly its a binary tree, not a binary search tree.
    laserlight's question was actually a really good hint. Forget what the previous recursive call might have been, in fact forget that it is recursive at all for one minute, in fact forget that you even wrote it. Just look at the code posted and ask yourself "What happens if node == NULL?".
    In particular, pay attention to the return type of the function.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ std routines
    By siavoshkc in forum C++ Programming
    Replies: 33
    Last Post: 07-28-2006, 12:13 AM
  2. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  3. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 08:09 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21