CODEWITHSUNDEEP
calgorithmtreetraversaln-ary-tree
Lin
Lin

Reputation: 1203

Traverse n-Ary tree Level Order

Let the structure given by:

// Struct to nAry tree
struct nNode {
  int val;                  // Some value (in future use a pointer to some data)
  struct nNode *next;       // Siblings of the same parent if next == NULL is the last
  struct nNode *prev;       // Siblings of same parent if prev == NULL is the first
  struct nNode *parent;     // Points to parent, if NULL is the root 
  struct nNode *children;   // Child node, other childs are found by moving next/prev
                            // if NULL is a leaf node
};

The code below should give the Traverse in Level

void nNode_traverse_levelOrder(struct nNode *node)
{
  struct nNode *child;
  struct nNode *sibling;
  struct nNode *head;

  struct QueueLL *queue;
  queue = newQueueLL();

  // Queue the root node
  enqueueLL(queue, node);

  while (! isQueueEmptyLL(queue)) {
    head = dequeueLL(queue);

    if(head) {
      visit(head);

      sibling = head->next;
      // Queue all brothers
      while(sibling) {
        enqueueLL(queue, sibling);
        sibling = sibling->next;
      }

      // Queue the children (there is only one)
      child = head->children;
      if (child) 
        enqueueLL(queue, child);
    }
  }
  destroyQueueLL(queue);
  queue = NULL;
}

Given the tree:

  /*                      1
   *            /---------|--------\
   *          2           3         4
   *        /   \                 /
   *      5       6              7
   */

It returns 

Node val: 1
Node val: 2
Node val: 3
Node val: 4
Node val: 5
Node val: 4
Node val: 7
Node val: 6
Node val: 7

But the expected is 1 2 3 4 5 6 7. I have double checked with Pre, Pos and In order traverse functions and all of them returns correctly, as below:

PRE 1 2 _5 _6 _3 4 _7

POS _5 _6 2 _3 _7 4 1

IN _5 2 _6 1 _3 _7 4

Looking to figure out what can be misleading me in my function

Upvotes: 1

Views: 1045

Answers (1)

Ry-
Ry-

Reputation: 224922

When you visit a node, you’re enqueuing all siblings following it. The next sibling will enqueue the rest of the siblings again. If you have an operation that can add an element to the beginning of the queue, you can use that after enqueuing the child:

if (sibling) {
  pushLL(queue, sibling);
}

Or just enqueue children instead of siblings, which is the usual way and makes for a much shorter function:

void nNode_traverse_levelOrder(struct nNode* node) {
  struct QueueLL* queue = newQueueLL();

  enqueueLL(queue, node);

  while (!isQueueEmptyLL(queue)) {
    struct nNode* head = dequeueLL(queue);

    visit(head);

    for (struct nNode* child = head->children; child != NULL; child = child->next) {
      enqueueLL(queue, child);
    }
  }

  destroyQueueLL(queue);
}

Upvotes: 2

Related Questions