CODEWITHSUNDEEP
cperformancedata-structurestree
overexchange
overexchange

Reputation: 1

Left Child Right Sibling tree - Depth First Search - Performance

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;

enter image description here

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)?

Upvotes: 2

Views: 2009

Answers (1)

Stefan Haustein
Stefan Haustein

Reputation: 18793

  1. 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.

  2. 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

Upvotes: 2

Related Questions