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 <iostream>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();};#endifPQ.C:#include PQ.hPQ::PQ(){    root = NULL;}PQ::~PQ(){    DeletePQ();}void PQ::DeletePQ(){    DeletePQ(root);}void PQ::DeletePQ(Node * node){    if(node != NULL)    {        DeletePQ(node->left);        DeletePQ(node->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 < node->value)    {        if(node->left != NULL)        {            Push(value, node->left);        }        else        {            node->left = new Node(value);        }    }    else    {        if(node->right != NULL)        {            Push(value, node->right);        }        else        {            node->right = new Node(value);        }    }}int PQ::Pop(){    int value;    if(root != NULL)    {        if(root->right != NULL)        {            value = Pop(root->right, root);        }        else        {            value = root->value;            if(root->left != NULL)            {                Node * temp = root;                root = root->left;                delete temp;            }            else            {                delete root;                root = NULL;            }        }    }    else    {        value = -1;    }    return value;}int PQ::Pop(Node * node, Node * parent){    int value;    if(node->right != NULL)    {        value = Pop(node->right, node);    }    else    {        value = node->value;        if(node->left != NULL)        {            parent->right = node->left;        }        else        {            parent->right = NULL;        }        delete node;    }    return value;}bool PQ::IsEmpty(){    bool isEmpty;    if(root == NULL)    {        isEmpty = true;    }    else    {        isEmpty = false;    }    return isEmpty;}
Priority Queue (Binary Search Tree) Implementation
c++;tree;binary search;priority queue
Handling booleansComputation 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 tobool PQ::IsEmpty(){    return root == NULL;}Pop return on failureReturning -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 PushPush doesn't need to be recursive:void PQ::Push(int value, Node * node){    while (1) {        if (value < node->value) {            if (node->left) {                node = node->left;            } else {                node->left = new Node(value);                return;            }        } else {            if (node->right) {                node = node->right;            } else {                node->right = new Node(value);                return;            }        }    }}Recursive PopPop needs not to be recursive either:int PQ::Pop(Node * node, Node * parent){    while (node->right) {        parent = node;        node = node->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 < node->value) {                if (node->left) {                    node = node->left;                } else {                    insertionPoint = &node->left;                }            } else {                if (node->right) {                    node = node->right;                } else {                    insertionPoint = &node->right;                }            }        }        *insertionPoint = new Node(value);    }