Member Avatar for bgx90

Can anyone tell me why my recursive find function for a binary search tree isn't working? It keeps returning false when searching for items that are in the tree. Thanks.

template<class T>
bool BST<T>::find(const T& sitem) const{
  //Precondition:
  //  A binary search tree exists
  //
  //Postcondition:
  //  If item is in the BST, true is returned, else false is returned
  //  A BST exists

  return find_R(sitem, root);
}


template<class T>
bool BST<T>::find_R(const T& sItem, TreeNode<T> *node) const{
  //Recursive function used by find
  //Precondition:
  //  A binary search tree exists
  //
  //Postcondition:
  //  If the search item is found, true is returned, else false is returned
  //  A BST exists

  if (node == NULL)
    return false;
  
  else if (node->item == sItem)
    return true;

  else if (node->item < sItem)
    return find_R(sItem, node->left);

  else if (node->item > sItem)
    return find_R(sItem, node->right);
}
  • 1 Contributor
  • 1 Reply
  • 101 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by bgx90

Dani AI

Generated

Good catch, — the symptom you described (always returning false for existing items) is exactly what happens when the comparison branches are flipped. With the wrong direction the search keeps going down the wrong child and eventually hits NULL even though the item is present.

Quick checks and debugging steps that catch this kind of bug fast:

  • Add simple visit logging (or breakpoints) to show each node value visited during a search. The path will reveal the wrong turn immediately.
  • Build a tiny, deterministic tree (5 nodes) and step through searches for root, leftmost, rightmost and a known internal node. If a search for a node you just inserted goes the other way, the comparisons are wrong.
  • Verify the BST invariant with an in-order traversal; that should produce a sorted sequence. If not, insertion/search logic is inconsistent.
  • Add a unit test that fails before the fix and passes after. That prevents regressions.

Other practical notes:

  • Decide and document how duplicates are handled (store equal keys consistently left or right, or forbid them). Search must follow the same rule used by insert.
  • Ensure comparison operators are consistent: operator< used by the tree and operator== (or the equality check) must reflect the same ordering. If a custom comparator is used on insert, use it on search too.
  • For very deep trees consider an iterative search (no recursion) or self-balancing trees to avoid stack depth issues and make the logic easier to reason about.

The core lesson is clarity: prefer clear naming and small, repeatable tests around insertion and lookup. That makes the kind of flipped-comparison mistake you found trivial to spot and hard to reintroduce.

Member Avatar for bgx90

I found the problem. The conditions of the if statements on lines 30 and 33 of find_R were wrong.
Should be

else if (sItem < node->item)
    return find_R(sItem, node->left);

  else if (sItem > node->item)
    return find_R(sItem, node->right);

Another case of not seeing the forest for the trees.

Edited by bgx90 because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.