title: Binary Search Tree Problem
body: <p>Why the search and successor and predecessor returns -1?</p>
  
  <pre><code>    // BST.cpp : main project file.
  
      #include "stdafx.h"
      #include &lt;cstdlib&gt;
      #include &lt;iostream&gt;
      #define SIZE 10
      using namespace std;
  
      struct Node {
          int value;
          Node *left;
          Node *right;
          Node *parent;
      };
  
      struct BST {
          Node *root;
      };
  
      void insert(int value, BST *tree) {
          Node *x = tree-&gt;root;
          Node *y = NULL;
          Node *z = (Node *) malloc(sizeof(Node));
          z-&gt;left = NULL;
          z-&gt;right = NULL;
          z-&gt;value = value;
  
          // Add your code here
          while (x!=NULL){
                y=x;
                if (z-&gt;value &lt; x-&gt;value)
                   x= x-&gt;left;
                else x = x-&gt;right;
          }
          z-&gt;parent=y;
          if (y==NULL)
             tree-&gt;root=z;
          else if (z-&gt;value &lt;y-&gt;value)
               y-&gt;left =z;
          else y-&gt;right =z;
  
      }
  
      Node *search(int key, Node *n) {
          if (n== NULL || key == n-&gt;value)
              return n;
  
          if (key &lt; n-&gt;value)
              search(key, n-&gt;left);
          else
              search(key, n-&gt;right);
      }
  
      Node *min(Node *n) {
          if (n == NULL || n-&gt;left == NULL)
              return n;
          else
              return min(n-&gt;left);
      }
  
      Node *max(Node *n) {
          if (n == NULL || n-&gt;right == NULL)
              return n;
          else
              return max(n-&gt;right);
      }
  
      Node *successor(int value, Node *n) {
          Node *y = NULL;
  
          Node *x = search(value, n);
  
          if (x == NULL)
              return NULL;
  
          if (x-&gt;right != NULL)
              return min(x-&gt;right);
  
          y = x-&gt;parent;
          while (y != NULL &amp;&amp; x == y-&gt;right) {
              x = y;
              y = y-&gt;parent;
          }
          return y;
      }
  
      Node *predecessor(int value, Node *n) {
          Node *x = search(value, n);
          Node *y = NULL;
          if (x == NULL)
              return NULL;
  
          if (x-&gt;left != NULL)
              return max(x-&gt;left);
  
          y = x-&gt;parent;
          while (y != NULL &amp;&amp; x == y-&gt;left) {
              x = y;
              y = y-&gt;parent;
          }
          return y;
      }
  
      Node *remove(int value, BST *tree) {
          Node *z = search(value, tree-&gt;root);
          Node *y = NULL, *x = NULL;
  
          if (z == NULL) return NULL;
  
          if (z-&gt;left == NULL || z-&gt;right == NULL)
              y = z;
          else
              y = successor(value, z);
  
          if (y-&gt;left != NULL)
              x = y-&gt;left;
          else
              x = y-&gt;right;
  
          if (x != NULL)
              x-&gt;parent = y-&gt;parent;
  
          if (y-&gt;parent == NULL)
              tree-&gt;root = x;
          else if (y == y-&gt;parent-&gt;left)
              y-&gt;parent-&gt;left = x;
          else
              y-&gt;parent-&gt;right = x;
  
          if (y != z) {
              int tmp = z-&gt;value;
              z-&gt;value = y-&gt;value;
              y-&gt;value = tmp;
          }
  
          return y;
      }
  
      // ascending sort function
      void sortAsc(Node *node) {
          //Add your code here
          //inorder
          if (node-&gt;left!=NULL)
             sortAsc(node-&gt;left);
          cout&lt;&lt;node-&gt;value&lt;&lt;" ";
          if (node-&gt;right!=NULL)
             sortAsc(node-&gt;right);
  
      }
  
      // descending sort function
      void sortDes(Node *node) {
          // Add your code here
          //inorder
          if (node-&gt;right!=NULL)
             sortDes(node-&gt;right);
          cout&lt;&lt;node-&gt;value&lt;&lt;" ";
          if (node-&gt;left!=NULL)
             sortDes(node-&gt;left);
  
      }
  
      void clear(BST *tree) {
          Node *n = NULL;
  
          while (tree-&gt;root != NULL) {
              n = remove(tree-&gt;root-&gt;value, tree);
              free(n);
          }
      }
  
  
      int main() {
          int A[] = {3, 5, 10, 4, 8, 9, 1, 4, 7, 6};
  
          Node *node = NULL;
          BST *tree = (BST *) malloc(sizeof(BST));
          tree-&gt;root = NULL;
  
          // build BST tree
          cout &lt;&lt; "Input data:\n\t";
          for (int i=0; i&lt;SIZE; i++) {
              cout &lt;&lt; A[i] &lt;&lt; " ";    // by the way, print it to the console
              insert(A[i], tree);     // You need to complete TASK 1, so that it can work
          }
  
          // sort values in ascending order
          cout &lt;&lt; "\n\nAscending order:\n\t";
          sortAsc(tree-&gt;root);        // You need to complete TASK 2. Otherwise you see nothing in the console
  
          // sort values in descending order
          cout &lt;&lt; "\n\nDescending order:\n\t";
          sortDes(tree-&gt;root);        // TASK 2 also!
  
          // Find minimum value
          if (tree-&gt;root != NULL)
              cout &lt;&lt; "\n\nMin: " &lt;&lt; min(tree-&gt;root)-&gt;value;
  
          // Find maximum value
          if (tree-&gt;root != NULL)
              cout &lt;&lt; "\n\nMax: " &lt;&lt; max(tree-&gt;root)-&gt;value;
  
          // delete 4
          cout &lt;&lt; "\n\nDelete 4 and add 2";
          //free(remove(4, tree));    // You need to complete TASK 3, so that remove(int, BST *) function works properly
                                  // we also need to release the resource!!!
  
          // insert 2
          insert(2, tree);        // It belongs to TASK 1 too.
  
          cout &lt;&lt; "\n\nAscending order:\n\t";
          sortAsc(tree-&gt;root);        // TASK 2!!
  
          // Find the successor of 5, -1 means no successor
          node = search(5, tree-&gt;root);
          cout &lt;&lt; "\n\nSearch of 5 is: " &lt;&lt; (node != NULL?node-&gt;value:-1);
  
  
          // Find the successor of 5, -1 means no successor
          node = successor(5, tree-&gt;root);
          cout &lt;&lt; "\n\nSuccessor of 5 is: " &lt;&lt; (node != NULL?node-&gt;value:-1);
  
          // Find the predecessor of 5. -1 means no predecessor
          node = predecessor(5, tree-&gt;root);
          cout &lt;&lt; "\n\nPredecessor of 5 is: " &lt;&lt; (node != NULL?node-&gt;value:-1);
  
          cout &lt;&lt; "\n\n";
  
          // clear all elements
          clear(tree);            // delete all nodes and release resource
          free(tree);             // delte the tree too
          system("Pause");
      }
  </code></pre>