#include <iostream>
using namespace std;

struct HeapNode
{
    int val;
    HeapNode * left;
    HeapNode * right;

    HeapNode(int n, HeapNode * lptr, HeapNode * rptr)
	: val(n),
	  left(lptr),
	  right(rptr)
    { }
};

bool printLevel(HeapNode * t, int level)
{
    if (t == 0) {
	return false;
    }
    if (level == 0) {
	cout << t->val << " ";
	return true;
    }
    else {
	bool left = printLevel(t->left, level-1);
	bool right = printLevel(t->right, level-1);
	return left || right;
    }
}

void print(HeapNode * t)
{
    int level = 0;
    while (printLevel(t,level)) {
	cout << endl;
	level++;
    }
}

HeapNode * MinChild(HeapNode * T)
{
    if (T == 0)        return 0;
    if (T->left == 0)  return T->right;
    if (T->right == 0) return T->left;
    
    return T->left->val < T->right->val ? T->left : T->right;
}

bool IsHeapOrdered(HeapNode * T)
{
    HeapNode * min = MinChild(T);
    if (min == 0) return true;

    return T->val < min->val &&
	IsHeapOrdered(T->left) &&
	IsHeapOrdered(T->right);
    
}

void RemoveMin(HeapNode * & T)
// precondition: T is not NULL
{
    if (T != 0) {

	if (T->left == 0 && T->right == 0) {   // leaf?
	    delete T;
	    T = 0;
	}
	else {
	    HeapNode * min = MinChild(T);
	    T->val = min->val;
	    if (T->left == min) {
		RemoveMin(T->left);
	    }
	    else {
		RemoveMin(T->right);
	    }
	}
    }
}

int main()
{
    HeapNode * root =
	new HeapNode(2,
		     new HeapNode(4,
				  new HeapNode(7,
					       new HeapNode(9,0,0),
					       new HeapNode(15,0,0)),
				  new HeapNode(5,
					       new HeapNode(6,0,0),
					       0)),
		     new HeapNode(3,
				  new HeapNode(8,
					       new HeapNode(12,0,0),
					       0),
				  new HeapNode(11,0,0)));

    cout << "order = " << IsHeapOrdered(root) << endl;
    print(root);

    cout << "--" << endl;
    RemoveMin(root);
    cout << "order = " << IsHeapOrdered(root) << endl;
    print(root);

    cout << "--" << endl;
    RemoveMin(root);
    cout << "order = " << IsHeapOrdered(root) << endl;
    print(root);
    
    return 0;
}