title: How to find out if Binary Search Tree contains a node given by user
body: <p>I would like to create a bool method <strong>bool search(int)</strong> to find out if the BST(Binary Search Tree) contains the node given by user.</p>
  
  <p><strong>I know this algorithm:</strong><br>
  We start by comparing the number given by user with the number of the BST root. There are three possibilities:<br>
  1.given number is equal to the root - the search ends successfully, method returns true<br>
  2.given number is greater than the root - then we continue recursively on the right descendant (right subtree)<br>
  3.given number is less than the root - then we continue recursively on the left descendant (left subtree)</p>
  
  <p>I know the concept of this problem and how it should work but I still can not write the code that really works. Could you please help me to fix it?</p>
  
  <p>Here is my code (it doesn´t work but I think that the concept is correct):</p>
  
  <pre><code>#include &lt;process.h&gt;
  #include &lt;conio.h&gt;
  #include &lt;iostream&gt;
  #include &lt;cstdlib&gt;
  using namespace std;
  
  class BinarySearchTree
  {
      private:
          struct tree_node
          {
             tree_node* left;
             tree_node* right;
             int data;
          };
          tree_node* root;
      public:
          BinarySearchTree()
          {
             root = NULL;
          }
          void insert(int);
          bool isEmpty() const { return root==NULL; }
          bool search(int);
  
  };
  
  //----------------------------------------------------------
  void BinarySearchTree::insert(int d)
  {
      tree_node* t = new tree_node;
      tree_node* parent;
      t-&gt;data = d;
      t-&gt;left = NULL;
      t-&gt;right = NULL;
      parent = NULL;
    // is this a new tree?
    if(isEmpty()) root = t;
    else
    {
      //Note: ALL insertions are as leaf nodes
      tree_node* curr;
      curr = root;
      // Find the Node's parent
      while(curr)
      {
          parent = curr;
          if(t-&gt;data &gt; curr-&gt;data) curr = curr-&gt;right;
          else curr = curr-&gt;left;
      }
      if(t-&gt;data &lt; parent-&gt;data)
         parent-&gt;left = t;
      else
         parent-&gt;right = t;
    }
  
  
  }
  bool BinarySearchTree::search(int d)
  {
      if (d ==  tree_node* root)
          return true;
      else if (d &gt;  tree_node* root)
      {
          if (this-&gt;right != NULL)    // case it has right descendant
              this-&gt;right-&gt;search(d);
          else
              return false;
      }
      else
      {
          if (this-&gt;left != NULL)     // case it has left descendant
              this-&gt;left-&gt;search(d);
          else
              return false;
      }
  }
  
  //----------------------------------------------------------
  int main()
  {
      BinarySearchTree b;
      int ch,tmp,tmp1;
      while(1)
      {
         cout&lt;&lt;endl&lt;&lt;endl;
         cout&lt;&lt;" Binary Search Tree Operations "&lt;&lt;endl;
         cout&lt;&lt;" ----------------------------- "&lt;&lt;endl;
         cout&lt;&lt;" 1. Insertion/Creation "&lt;&lt;endl;
         cout&lt;&lt;" 2. Does BST contain this number? "&lt;&lt;endl;
         cout&lt;&lt;" 3. Exit "&lt;&lt;endl;
         cout&lt;&lt;" Enter your choice : ";
         cin&gt;&gt;ch;
         switch(ch)
         {
             case 1 : cout&lt;&lt;" Enter Number to be inserted : ";
                      cin&gt;&gt;tmp;
                      b.insert(tmp);
                      break;
             case 2 : cout&lt;&lt;" Enter number to be found : ";
                      cin&gt;&gt;tmp1;
                      b.search(tmp1);
                      break;
             case 3 : system("pause");
                      return 0;
                      break;
         }
      }
  }
  </code></pre>