#ifndef BSTNODE_HPP
#define BSTNODE_HPP


template<typename Data>
class BSTNode {

public:

  /** Constructor.  Initialize a BSTNode with the given Data item,
   *  no parent, and no children.
   */
  BSTNode(const Data & d): data(d) {
    left = right = parent = 0;
  }

  BSTNode<Data>* left;
  BSTNode<Data>* right;
  BSTNode<Data>* parent;
  int info;  // instance variable used in advanced algorithms
  const Data  data;

  /** Return the inorder successor of this BSTNode in a BST, or 0 if none.
   *  PRECONDITION: this BSTNode is a node in a BST.
   *  POSTCONDITION:  the BST is unchanged.
   *  RETURNS: the BSTNode that is the inorder successor of this BSTNode,
   *  or 0 if there is none.
   */ // TODO
  BSTNode<Data>* successor() {

      BSTNode<Data>* leftCurrentNode;
      BSTNode<Data>* upCurrentNode;


      // This covers the case where there is a right child
      if (this->right != 0) {
        if (this->right->left !=0) {
            leftCurrentNode = this->right->left;
            while (leftCurrentNode != 0) {
                leftCurrentNode = leftCurrentNode->left;
            }
            return leftCurrentNode;
            }
        return this->right;
      }

      // This covers the case where there is no right child
      else if (this->parent != 0) {
        if (this->parent->data < this->data) {
            upCurrentNode = this->parent;
            while (upCurrentNode->parent->data < this->data) {
                upCurrentNode = upCurrentNode->parent;
            }
            if (upCurrentNode->data > this->data) {
                return upCurrentNode;
            }
        }
      }
      return 0;
  }

};

#endif // BSTNODE_HPP