Left Child Right Sibling tree - Depth First Search - Performance

Question

For the below tree,

typedef struct SiblingTreeNode{
  void *item;
  struct SiblingTreeNode *parent;
  struct SiblingTreeNode *firstChild;
  struct SiblingTreeNode *nextSibling;
}SibTreeNode;

typedef struct Tree{
  SibTreeNode *root;
  int size; // number of nodes in tree
}Tree;

1)

Assuming the huge depth of a tree, To avoid stack overflow, Can we perform DFS without using recursion?

2)

Generally, a tree node has n child pointers and data pointer(item), From performance aspect of operations on tree, What are the advantages of maintaining sibling(nextSibling) and first child(firstChild) and parent pointer(parent)?

[This older question](http://stackoverflow.com/questions/14015525/what-is-the-left-child-right-sibling-representation-of-a-tree-why-would-you-us) addresses your second question. — templatetypedef, Dec 11 '16 at 18:59

Stefan Haustein · Answer 1 · 2016-12-12T19:20:05.407

2

Yes. It's always possible by using an explicit data structure instead as needed (e.g. your own explicit stack) to keep track of where you are or what you still need to do. A reason for doing this could be limited call stack space. Some languages support a simple case of recursion called "tail recursion" in a way that avoids stack overhead automatically.

Edit: In this specific case, you don't need to keep track of more than the current node, see code added below.
The advantage of the "left child / left sibling" structure is that you can have any number of children without the need of an additional data structure (e.g. a list or array) to manage the children. A disadvantage is that you can't directly access the nth child -- accessing the nth child is a O(n) operation.

Non-recursive DFS for the given data structure:

void Dfs(Tree* tree) {
  SiblingTreeNode* current = tree.root;

  while (current != nullptr) {

    visit (current);

    if (current->firstChild != nullptr) {
      current = current->firstChild;
    } else if (current->nextSibling != nullptr) {
      current = current->nextSibling;
    } else {
      do {
        current = current->parent;
      } while (current != nullptr && current->nextSibling == nullptr);
      if (current != nullptr) {
         current = current->nextSibling;
      }
    }
  }  // while
}  // Dfs

edited Dec 12 '16 at 19:20

answered Dec 11 '16 at 23:39

Stefan Haustein

18,427
3
36
51

Explicit or implicit, stack depth will still be `O(logN)`. – vgru Dec 11 '16 at 23:42
1

@Groo Not necessarily - it depends on the depth of the tree. – templatetypedef Dec 12 '16 at 00:03
@templatetypedef: my point was that (in big-O notation) space complexity doesn't depend on whether you simply rewrite the algorithm to use an explicit stack. So, yes, they both depend on the depth of the tree if we are not talking about a balanced binary tree. – vgru Dec 12 '16 at 11:57
@Groo no explicit data structure(like stack) usage is appreciated. Less memory. Can't we rely on parent pointer for DFS? – overexchange Dec 12 '16 at 12:54
Call stack memory is often more limited than heap memory, that's why it may make sense to use an explicit stack allocated on the heap, even if the memory consumption is the same. And the original question was just if recursion can be avoided. That said, a stack might not be needed here, you probably can use a variation of a "follow the wall" maze navigation algorithm, i.e. just keep track if you are going up or down to make sure you don't enter an endless loop when you re-visit the same node on the way back... – Stefan Haustein Dec 12 '16 at 13:43
@StefanHaustein Are you asking to maintain a visit flag for each node? Can you please clarify? We maintain network hierarchy in such tress. So, in NSM applications that I work, If I use stack in heap, then .... – overexchange Dec 12 '16 at 13:52
1

I have added an implementation. Having a parent pointer saves you from needing an explicit stack. – Stefan Haustein Dec 12 '16 at 18:49

Left Child Right Sibling tree - Depth First Search - Performance

1 Answers1