searching a binary tree

Question

I'm writing an iterative function to search a binary tree for a certain value. This is localized to signed ints until I get into how to genericize classes.

Assume that my class is BinarySearchTree, and it has a pointer to the root node of the tree. Also assume that nodes are inserted through an insert function, and have pointers to two children. Here is a much abbreviated version of the Node struct:

struct Node
{
   public:
      Node *left_, *right_;
      int value_

      Node(int val) : value_(val), left_(0), right_(0) { }
      //done in this manner to always make sure blank children are
      //init to zero, or null
      Node(int val, Node *left, Node *right) : value_(val), left_(0), right_(0) 
          { left_ = left; right_ = right; } 
}

So, you can safely assume that a node's uninit pointers will be NULL.

Here is my code:

int BinarySearchTree::search(int val)
{
    Node* next = this->root();

    while (next->left() != 0 || next->right () != 0)
    {
        if (val == next->value())
        {
            return next->value();
        }    
        else if (val < next->value())
        {
            next = next->left();   
        }
        else if (val > next->value())
        {
            next = next->right();
        }
    } 

    //not found
    return 0;
}

This code is being rejected by a friend for two reasons:

1) If next has no children, both will evaluate to zero and I will prematurely exit the loop (I will never check the searched val against next's value).

2) If next has one child, but the data you are searching for should be on the empty side of the tree, next will be set to 0, and it will loop again, comparing next (which is 0) to the left and right trees like while(0->left()), resulting in undefined behavior.

I am told that the solution to both problems lies in the loop condition, but I can't see what I can do to easily remedy the situation. Can the community of Stack Overflow offer any insights?

Answer 1

while (next != NULL) ?

Answer 2

I think you should be testing if next is not NULL in your loop like so:

int BinarySearchTree::search(int val)
{
    Node* next = this->root();

    while (next)
    {
        if (val == next->value())
        {
            return next->value();
        }    
        else if (val < next->value())
        {
            next = next->left();   
        }
        else if (val > next->value())
        {
            next = next->right();
        }
    } 

    //not found
    return 0;
}

Answer 3

First of all, I'm not sure why you are returning an int. What if you are searching for 0 in the tree. You probably want something like this:

bool BinarySearchTree::Search(int val) {
  Node* current = root();
  while (current != NULL) {
    // Check if it's here
    if (val == current->value()) {
      return true;
    }
    if (val < current->value()) {
      current = current->left();
    } else {
      current = current->right();
    }
  }
  // Not found
  return false;
}

Notice that the loop invariant: at the beginning of each loop, you are at a non null node that you need to "process". First check if it's the node you want. If not, make a branch, and let the loop decide if the branch was "good" (ie - non null). Then you'll let the next loop iteration take care of testing.