Priority Queue (Binary Search Tree) Implementation
Handling booleans

Computation of isEmpty is anti-idiomatic. Consider

    isEmpty = (root == NULL);


Now it is easy to see that isEmpty is not needed at all. The whole method can be shortened to

bool PQ::IsEmpty()
{
    return root == NULL;
}

Pop return on failure

Returning -1 on failure means that the tree cannot have nodes with  -1 as a value (a caller cannot tell such node from a failure). Consider throwing an exception instead.
Recursive Push

Push doesn't need to be recursive:

void PQ::Push(int value, Node * node)
{
    while (1) {
        if (value &lt; node-&gt;value) {
            if (node-&gt;left) {
                node = node-&gt;left;
            } else {
                node-&gt;left = new Node(value);
                return;
            }
        } else {
            if (node-&gt;right) {
                node = node-&gt;right;
            } else {
                node-&gt;right = new Node(value);
                return;
            }
        }
    }
}

Recursive Pop

Pop needs not to be recursive either:

int PQ::Pop(Node * node, Node * parent)
{
    while (node-&gt;right) {
        parent = node;
        node = node-&gt;right;
    }
    do_actual_deletion
}



Edit: as requested, no multiple returns, no infinite loops. I am not sure it is cleaner than the original.

    void PQ::Push(int value, Node * node)
    {
        Node ** insertionPoint = 0;
        while (insertionPoint == 0) {
            if (value &lt; node-&gt;value) {
                if (node-&gt;left) {
                    node = node-&gt;left;
                } else {
                    insertionPoint = &amp;node-&gt;left;
                }
            } else {
                if (node-&gt;right) {
                    node = node-&gt;right;
                } else {
                    insertionPoint = &amp;node-&gt;right;
                }
            }
        }
        *insertionPoint = new Node(value);
    }