4
$\begingroup$

Below is the code,

class SibTreeNode extends TreeNode {
  protected Object item;
  protected SibTreeNode parent;
  protected SibTreeNode firstChild;
  protected SibTreeNode nextSibling;

  .....
}

As per below diagram, I could not understand the purpose of parent member in every node.

enter image description here

Why do we require parent member in every node? Does it improve space/time complexity of insert/find/update operation?

Note: Beginner in Data-structure

$\endgroup$
  • 3
    $\begingroup$ parent pointer is not necessary. but it may help you in traversal / data processing. ie. traversal from leaf to root, propagate child data to parent, retrieve parent data from child, etc. so it is usually kept in node structure. $\endgroup$ – Terence Hang Sep 15 '15 at 13:32
  • $\begingroup$ @TerenceHang not necessary in the sense? Does parent not add any performance enhancement for any insert/update/find/delete operation? $\endgroup$ – overexchange Sep 15 '15 at 21:24
  • 1
    $\begingroup$ Please don't change the question to something completely different after you've been given answers. Now Yuval's wasted some time writing up his answer. (I think the new version is the better question, though, so I'll let it stand.) $\endgroup$ – Raphael Sep 16 '15 at 7:08

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.