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$ Apr 19, 2020 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$ Apr 19, 2020 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, 2020 at 23:55

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.