gistfile1.hpp

#include <stdio.h>

class Node {
  public:
    int value;
    Node* left;
    Node* right;

    Node() {
      left = NULL;
      right = NULL;
    }

    // should do some cleanup code here too, but I'm lazy
};

Node* root;

/* Build a tree that looks like this:

        5
       / \
      3   6
     / \   \
    2  4   7
   /
  1

*/
void populateTree() {
  root = new Node();
  root->value = 5;

  root->left = new Node();
  root->left->value = 3;

  root->left->left = new Node();
  root->left->left->value = 2;

  root->left->left->left = new Node();
  root->left->left->left->value = 1;

  root->left->right = new Node();
  root->left->right->value = 4;

  root->right = new Node();
  root->right->value = 6;

  root->right->right = new Node();
  root->right->right->value = 7;
}

// print the contents of the node and children in order
void printInOrder(Node* node) {
  if (node->left != NULL) {
    printInOrder(node->left);
  }

  printf("%d ", node->value);

  if (node->right != NULL) {
    printInOrder(node->right);
  }
}

void printInOrder() {
  printInOrder(root);
}

void removeMin() {
  Node* prev = NULL;
  Node* node = root;
  // find left-most node (i.e. smallest value)
  while (node->left != NULL) {
    prev = node;
    node = node->left;
  }

  if (node->right == NULL) {
    // right child is null, so we are a leaf node - just delete this node
    if (prev != NULL) {
      prev->left = NULL;
    }
    else {
      // we're at root, so set root to null
      root = NULL;
    }
  }
  else {
    // right child is not null, so delete this node and move the child to its place
    if (prev != NULL) {
      prev->left = node->right;
    }
    else {
      // we're at root, so promote the child to root
      root = node->right;
    }
  }
}

int main() {
  printf("Building tree...\n");
  populateTree();
  printf("Printing tree...\n");
  printInOrder();
  printf("\n");
  printf("Deleting smallest...\n");
  removeMin();
  printf("Printing tree...\n");
  printInOrder();
  printf("\n");

  return 0;
}