Priority Queue (Binary Search Tree) Implementation I have made a Priority Queue implemented as a Binary Search Tree. I would appreciate comments related to optimization and proper functionality, but any comments/critiques are welcome.

PQ.h:

#ifndef PQ_H
#define PQ_H

#include &lt;iostream&gt;

struct Node
{
    int value;
    Node * left;
    Node * right;
    Node(int value)
    : value(value), left(NULL), right(NULL)
    {

    }
};

class PQ
{
    private:
        Node * root;
        void Push(int value, Node * node);
        int Pop(Node * node, Node * parent);
        void DeletePQ(Node * node);
    public:
        PQ();
        ~PQ();
        void Push(int value);
        int Pop();
        void DeletePQ();
        bool IsEmpty();
};

#endif


PQ.C:

#include "PQ.h"

PQ::PQ()
{
    root = NULL;
}

PQ::~PQ()
{
    DeletePQ();
}

void PQ::DeletePQ()
{
    DeletePQ(root);
}

void PQ::DeletePQ(Node * node)
{
    if(node != NULL)
    {
        DeletePQ(node-&gt;left);
        DeletePQ(node-&gt;right);
        delete node;
    }
}

void PQ::Push(int value)
{
    if(root != NULL)
    {
        Push(value, root);
    }
    else
    {
        root = new Node(value);
    }
}

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

int PQ::Pop()
{
    int value;
    if(root != NULL)
    {
        if(root-&gt;right != NULL)
        {
            value = Pop(root-&gt;right, root);
        }
        else
        {
            value = root-&gt;value;
            if(root-&gt;left != NULL)
            {
                Node * temp = root;
                root = root-&gt;left;
                delete temp;
            }
            else
            {
                delete root;
                root = NULL;
            }
        }
    }
    else
    {
        value = -1;
    }
    return value;
}

int PQ::Pop(Node * node, Node * parent)
{
    int value;
    if(node-&gt;right != NULL)
    {
        value = Pop(node-&gt;right, node);
    }
    else
    {
        value = node-&gt;value;
        if(node-&gt;left != NULL)
        {
            parent-&gt;right = node-&gt;left;
        }
        else
        {
            parent-&gt;right = NULL;
        }
        delete node;
    }
    return value;
}

bool PQ::IsEmpty()
{
    bool isEmpty;
    if(root == NULL)
    {
        isEmpty = true;
    }
    else
    {
        isEmpty = false;
    }
    return isEmpty;
}
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);
    }