2

In the below tree,

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

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

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?

Improve this question

1 Answer 1

Reset to default
3

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.

Improve this answer
10
  • 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?
    – overexchange
    Dec 12, 2016 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.
    – candied_orange
    Dec 12, 2016 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.
    – overexchange
    Dec 16, 2016 at 9:02
  • Not if you traverse iteratively.
    – candied_orange
    Dec 17, 2016 at 0:24
  • Iteratively without parent pointer?
    – overexchange
    Dec 17, 2016 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.