0
$\begingroup$

Is it a good idea to store a pointer to the parent node in a binary search rather than to find the parent node several times?

struct BSTNode
{
    Node* leftChild;
    Node* rightChild;
    Node* parent;     //nullptr for root
    int data;
};

or

struct BSTNode
{
    Node* leftChild;
    Node* rightChild;
    int data;
    Node* findParent(Node* root);
};
$\endgroup$
3
  • $\begingroup$ It depends on the application. No clear-cut answer. $\endgroup$ – Yuval Filmus Apr 19 '20 at 15:59
  • $\begingroup$ That said, if space is not at premium, you probably don't lose much by having one more field in your data structure. $\endgroup$ – Yuval Filmus Apr 19 '20 at 16:00
  • $\begingroup$ I don't think this is answerable, since you don't define what criteria you would use for judging whether it is a "good idea" or what context you're using the data structure in. As such, the only answers you're likely to get are "it depends" or answers that are a matter of opinion. $\endgroup$ – D.W. Apr 19 '20 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.