In the below tree,

typedef struct lcrsNode{
   void *item;
   struct lcrsNode *parent;
   struct lcrsNode *firstChild;
   struct lcrsNode *nextSibling;

typedef struct Tree{
   lcrsNode *root;
   int size; // Number of nodes;

enter image description here

What are the advantages of maintaining parent pointer in a tree node? Does it help in performing DFS without recursion or explicit stack?


DFS or Depth First Search is a form of tree traversal

enter image description here

DFS means you descend the children as far as you can then climb back up to the parent to do it again (see dotted line). That's hard to do if the node doesn't point to the parent. If it doesn't you have to somehow remember where the parent is, with say, recursion or an explicit stack. If the node knows its parent then simple iteration is enough to implement a DFS.

If this is for a homework assignment remember your instructor can search and find this as easily as you can. Show you can think about this for yourself.

  • I know, In NMS applications that I worked on, it is fatal to use recursion or explicit stack. One supple question, Could you think about morris traversal to do DFS over maintaining parent pointer?When to use morris traversal? Dec 12 '16 at 18:03
  • Morris traversal requires write access and should be done transactionally because getting interrupted in the middle (an exception, a crash, a power failure) leaves the tree in a bad state. Also means other threads will get confused if they try to read the tree while you're fiddling around. Long as I don't care about any of that I like Morris fine. Whether I care depends entirely on the problem I'm trying to solve. Dec 12 '16 at 18:13
  • But still, when you visited Node A, you have the call stack from root to leaf, which will crash in huge depth trees. Dec 16 '16 at 9:02
  • Not if you traverse iteratively. Dec 17 '16 at 0:24
  • Iteratively without parent pointer? Dec 17 '16 at 0:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.