/* Hidden stub code will pass a root argument to the function below. Complete the function to solve the challenge. Hint: you may want to write one or more helper functions.

The Node struct is defined as follows:
   struct Node {
      int data;
      Node* left;
      Node* right;
   }
*/
   vector<int> leftNodes;
   vector<int> rightNodes;
   int treeDepth = 0;

   bool CheckNode(Node* root) {
       for (int currentNode : leftNodes) {
           if (root->data >= currentNode) {
               return false;
           }

       }

       for (int currentNode : rightNodes) {
           if (root->data <= currentNode) {
               return false;
           }
       }

       if (root->left != nullptr && root->right != nullptr) {
           if (root->data <= root->left->data || root->data >= root->right->data) {
               return false;
           }
       }

       return true;
   }

   void RemoveNode(bool _isLeft) {
     if (_isLeft) {
         leftNodes.pop_back();
     }
     else {
         rightNodes.pop_back();
     }
   }

   void AddNode(int _value, bool _isLeft) {
     if (_isLeft) {
         leftNodes.push_back(_value);
     }
     else {
         rightNodes.push_back(_value);
     }
   }

   bool checkBST(Node* root) {
     treeDepth++;

     if (root->left != nullptr && root->right != nullptr) {
         if (!CheckNode(root)) {
             return false;
         }

         AddNode(root->data, true);

         if (!checkBST(root->left)) {
             return false;
         }

         AddNode(root->data, false);
         RemoveNode(true);

         if (treeDepth == 1) {
            rightNodes.clear();
            leftNodes.clear();
            AddNode(root->data, false);
         }

         if (!checkBST(root->right)) {
             return false;
         }
         RemoveNode(false);

     }
     else {
         if (!CheckNode(root)) {
             return false;
         }
     }

     treeDepth--;
     return true;
   }