StackOverFlowException in BST algorithm

I have been trying to implement a Contains method into my BSTree class that will accept a value and then check through all of the nodes to see if it is contained in the tree. I think that the algorithm is correct, but I don't know why I keep getting a StackOverFlowException at the first if statement. Any ideas?

public Boolean Contains(T item)
    {
      Node<T> node = root;
      return contains(root, item);
    }



开发者_Python百科    private Boolean contains(Node<T> node, T item)
    {
      if (item.CompareTo(root.Data) == 0)
      {
        return true;//return 0 if found
      }
      else
      {
        if (item.CompareTo(root.Data) > 0)
        {
          //root = node.Left;
          Node<T> left = root.Left;
          return(contains(root, item));
        }
        else
        {
          if (item.CompareTo(root.Data) < 0)
          {
            //root = node.Right;
            Node<T> right = root.Right;
            return(contains(root, item));
          }
          else
          {
            return false;//return 1 if not found
          }
        }        
      }
    }

The problem with your code is that you're passing the wrong node into the recursive calls. Suppose, for example, that your element is smaller than everything in the tree. Then on the first recursive call, you'll hit this statement:

Node<T> left = root.Left;
return(contains(root, item));

This means that you recurse on the root, not the left child. Thus on the next iteration, you'll find that the element is smaller than the right child of the root, and so you'll execute the exact same statement again, recursively calling the same function repeatedly until you run out of stack space.

To fix this, you should change the above code to read

Node<T> left = node.Left;
return(contains(left, item));

This says to look in the left subtree of the current node, not the root node itself. Similarly, you'll need to update the corresponding case for the right branch.

Finally, to finish this off, you'll need to add a base case to your recursive function that handles the case where the tree is null, either because you've walked off the tree or the tree was empty to begin with. I'll leave this as an exercise. :-)

your logic is incorrect . It will not go to the return false statement.

private Boolean contains(Node<T> node, T item)
    {
      if (item.CompareTo(root.Data) == 0)
      {
        return true;//return 0 if found
      }
      else///if 0 <> 
      {
        if (item.CompareTo(root.Data) > 0)  //if 0<
        {
          //root = node.Left;
          Node<T> left = root.Left;
          return(contains(root, item));
        }
        else  //if 0>
        {
          if (item.CompareTo(root.Data) < 0) if // 0>
          {
            //root = node.Right;
            Node<T> right = root.Right;
            return(contains(root, item));
          }
          else  // this will be not executed ever
          {
            return false;//return 1 if not found
          }
        }        
      }
    }

You don't need recursion. You can just iterate so you don't geta StackOverflow even if you have a huge tree.

public Boolean Contains(T item) {
    Node<T> currentNode = root;

    while(currentNode != null) { // Or whatever you use to signal that there is no node.
        switch(item.CompareTo(currentNode.Data)) {
            case -1:
                currentNode = currentNode.Right;
                break;
            case 1:
                currentNode = currentNode.Left;
                break;
            default: // case 0
                return true;
        }
    }
    return false;
 }