BST Problems

bst.cc

/* Question
 *  
 *  Given a binary search tree (BST), write the following two methods:
 *   
 *   1. Given a pointer to a node in the tree, find the smallest element.
 *   2. Given a pointer to a node in the tree, find the next highest element in key value.
 *   3. Do an in-order traversal of the tree
 *   */

struct Node {
   int data;
   Node *parent;
   Node *left;
   Node *right;
};

// Pre-req of having an existing parent
bool isRightChild(Node *cur) {
   return cur->parent->right == cur;
}

bool isNotRoot(Node *cur) {
   return cut->parent != NULL;
}


Node *getSmallest(Node *cur) {
   while(cur->left != NULL) {
      cur = cur->left;
   }
   return cur;
}


Node *getNextHighest(Node *cur) {
   // NULL case catch
   if(cur == NULL) {
      return NULL;
   }

   // If there is a right child
   if(cur->right != NULL) {
      return getSmallest(cur->right);
   }

   // We are done if it's the root and there is no right subtree
   if(!isNotRoot(cur)) {
      // No next highest value
      return NULL;
   }

   // Use the parent if we are a left child
   if(!isRightChild(cur)) {
      return cur->parent;
   }
   else {
      // Go up until we find a node that is a left child or run out
      while(isNotRoot(cur) && isRightChild(cur)) {
         cur = cur->parent;
      }

      // Base case to end when we go back up to the root
      if(isNotRoot(cur)) {
         return NULL;
      }

      // We already saw this node while coming downwards so we go up one
      return cur->parent;
   }
}


void traverseTree(Node *root) {
   // Empty tree
   if(root == NULL) {
      cout << "Empty tree" << endl;
      return;
   }

   // Start at the smallest
   Node *cur = getSmallest(root);

   // Traverse until we exhaust all the nodes
   while(cur != NULL) {
      cout << cur->data << endl;
      cur = getNextHighest(cur);
   }
}