5
$\begingroup$

Consider a tree structured task list where intermediate nodes define sub-groupings of tasks but are not tasks themselves, and the leaves represent the actual tasks.

I want to traverse this type of tree giving equal opportunity/priority/time(?) for each group with respect to its parent.

For example, if the root have 3 sub-trees (node or leaf), first I want to complete 1 task from the first sub-tree, then complete another task from the second sub-tree, and finally complete a task from the third sub-tree. When all sub-trees processed, the algorithm would start from the beginning this time selecting the second task from the sub-trees. This way, all the sub-trees would have equal processing time in terms of tasks in a given time frame. The same requirement is also present in each sub-trees themselves recursively of course.

This might require keeping tabs of traversed child paths for each loop on each node. ... Maybe a recursive traversal could automatically handle this?

Consider the following tree structure as an example:

"Equal Opportunity" Tree Traversal Example

So the traversal I am thinking about would be as following for this example.

  1. Level 0 has no task, 3 sub-trees, go into first sub-tree to find a task
  2. We follow as in depth-first to arrive at task A and select it (complete it)
  3. Now the first sub-tree in level 1 has a task completed, while its siblings are at 0, so we select from the second sub-tree
  4. Level 1 second sub-tree has only one task, D, so we select it
  5. Similarly we go in to the third sub-tree and find the task F and select it
  6. Now we return to level 1 and try to find our second task from the first sub-tree
  7. IMPORTANT: We have already selected a task from level 1's first sub-tree, so we go into its second sub-tree and select task E
  8. Now level 1 first sub-tree has two tasks completed, and the second sub-tree has no other tasks, so we skip it and go into third sub-stree and select G
  9. Similary, we loop again and select B from left side, and I from right side (we don't select H because its sibling already selected)
    1. Then we select C from the left side completing this side and K from the right side (J is not selected similarly)
    2. Only the right is left, so we select first H and finally the J, completing our traversal.

Traversal of leaves: (A->D->F)->(E->G)->(B->I)->(C->K)->(H)->(J)

[Adding this clarifying paragraph from the comments:]

Essentially the algorithm prevents any sub-grouping getting ahead (more than 1 tasks) of its unfinished siblings. It might be considered, in part, as a hierarchical round-robin scheduling giving equal time in terms of task operations.

So my questions are:

  1. Is there a name for this kind of tree traversal. If not, what would you call it?

  2. How would you approach traversing this tree in an efficient way and what would be the complexity?

Big thanks!

EDIT: Changed "opportunity" to "opportunity/priority/time(?)" in text and removed it from the title.

UPDATE: I have used the final algorithm from Apass.Jack and compared some different trees on it. Calculating the complexity proved difficult, though it definitely looks lower than $O(n\log n)$,.

JS Code can be found as a:

Here are some execution results for different depths (D) and leaf counts (L):

          D3L10   | D3L1000 | D6L10 | D6L1000
          ===================================
Push      |  35   |   3350  |  50   |  4698 |
Unshift   |  14   |   1150  |  17   |  1549 |
Splice    |  35   |   3350  |  50   |  4698 |
Access    |  35   |   3350  |  50   |  4698 |
Traverse()|  16   |   1351  |  20   |  1808 |
Zip()     |   5   |    151  |   8   |   550 |
          -----------------------------------

NOTE: My question traversed siblings in left to right order but as Apass.Jack has stated below, a randomized recursive round-robin (RRRR) algorithm would indeed be more useful in task-management situation and current algorithm could be modified to do that easily.

$\endgroup$
2
  • $\begingroup$ Instead of "equal opportunity", "equal priority" will be a better phrase since what you have described is the equal opportunity to be the very next one to be selected in the search path. I could claim "Equal opportunity" even if the subtrees are always selected from left to right on each level since no subtree is excluded and no subtree get more than one opportunity. $\endgroup$
    – John L.
    Aug 4, 2018 at 20:44
  • $\begingroup$ @Apass.Jack That's a good point. Essentially the algorithm prevents any sub-grouping getting ahead (more than 1 tasks) of its unfinished siblings. It might be considered, in part, as a hierarchical round-robin scheduling giving equal time in terms of task operations. "Equal priority" or "Equal time" could both be better in that sense. I will add this note into my question. Thanks! $\endgroup$ Aug 5, 2018 at 10:36

2 Answers 2

2
$\begingroup$

If we just mark a leaf as visited in this round instead of removing it so as to allow it to be listed in the next round, we will get an algorithm to traverse tree leaves with repetitions, which is called "recursive round robin scheduler" in the case of binary trees in a paper in Computer Networks in 1999, which I would also call "recursive round robin tree leaf sampling with replacement".

So I would call the output of the algorithm in OP's question "recursive round robin tree leaf sampling without replacement" or "RRR tree leaf traversal" or just "RRR traversal" in short. Indeed, I cannot think of any other algorithm that traverse tree leaves could rightfully claim being both "round robin" at subtrees of the same parent and "recursive".

(If the order in which each subtree of the same parent is selected is randomized instead of always left to right, we will have an algorithm that we may call recursive randomized round robin leaf traversal algorithm, or, an even more lovely abbreviation, RRRR traversal.)

Here is the pseudocode of my recursive algorithm that has the same output as OP's algorithm and its auxiliary zip procedure.

procedure rrrTraversal(rootedTree):
  if rootedTree is just a root without children
    return a list with rootedTree as its only element

  ll := an empty list of lists

  foreach subtree s of rootedTree from left to right:
    ss := rrrTraversal(s)
    push ss to the back of ll

  return zip(ll)

procedure zip(listOflists):
  zipped := an empty list

  while listOflists is not empty:
    foreach list li in listOflists from front to end:
      if li is not empty:
        fi := first item in li
        remove fi from li
        push fi to the back of the zipped
      else:
        remove li from listOflists

  return zipped

OP asks "This might require keeping tabs of traversed child paths for each loop on each node. ... Maybe a recursive traversal could automatically handle this?" The algorithm listed above gives a positive answer to that. It also fully justifies the usage of "recursive" in our description of the algorithm.

This algorithm may be refined by merging a parent with its only child whenever that situation, a parent with only one child, is encountered.

Here is a sample implementation in JavaScript.

The average complexity of the algorithm is probably $O(n\log n)$, because of the similarity of the algorithm to merge sort. However, it is not clear what will be the worst cases and what will be complexity of the worst cases.

It looks like it is nontrivial to find a significant faster algorithm than the recursive algorithm above. In particular, is there a linear algorithm in term of the number of the leaves? That should be a new question, though.

$\endgroup$
3
  • $\begingroup$ Thanks @Apass.Jack, I liked your "RRRR Tree Leaf Traversal" name proposal. But I am not sure how this algorithm should work, and that removing from a list while looping through it might not be safe. In fact, I tried to implement your solution in JS but it returns empty. I've tried with and without deep cloning the passed arrays. If you want to take a look: gist.github.com/cagils/9c90535821810cb9df577ed15ad62d9e. Online execution is here: tpcg.io/0YQ5zf $\endgroup$ Aug 23, 2018 at 18:48
  • 1
    $\begingroup$ Please check the newly-added base case of the recursion and a working implementation of my algorithm. $\endgroup$
    – John L.
    Aug 23, 2018 at 21:49
  • $\begingroup$ Updated algorithm works perfectly and now I understand your approach. It is really elegant. Too bad, JS does not have a proper zip function, then we could shorten that function to a one-liner, or maybe not(!) since it is not strictly a zipper, I've tried with map-reduce but no luck there :) I have added some execution results at the end of my question. The complexity looks like lower than n.log(n) but it is difficult to pinpoint as you have stated. I am now accepting your answer. Thanks for all your help with this. $\endgroup$ Aug 27, 2018 at 13:29
2
$\begingroup$

Here is a simple algorithm using a stable priority queue, where elements of equal priority will exit the queue in the order they are inserted into the queue.

  1. Let the priority of each node be its level, a.k.a. its depth from the root. Lower level means higher priority.
  2. Initialize $Q$ to be a stable priority queue of nodes containing the root.
  3. while $Q$ is not empty:
    1. Take a node $q$ from $Q$.
    2. while $q$ is not a leaf:
      1. Add $q$'s next right sibling, if any, to $Q$.
      2. Replace $q$ by its leftmost child.
    3. output $q$.

This traversal goes level by level, outputting the leftmost leaf of each subtree and keeping track of what to do next in each subtree in the stable priority queue. Note that the traversal uses each edge only once.

Here is a sample run of the algorithm.

1
├──2
│  ├──3
│  │  ├──A
│  │  ├──B
│  │  └──6
│  │     └──C
│  └──8
│     └──E
├──D
└──11
   ├──F
   └──13
      ├──14
      │  ├──G
      │  └──H
      ├──17
      │  └──18
      │     ├──I
      │     └──J
      └──K


Queue is not empty: [1]
1 has no more siblings.

Descending to the first child of 1: node 2
Added 2's sibling D to the queue.
The queue is now: [D]

Descending to the first child of 2: node 3
Added 3's sibling 8 to the queue.
The queue is now: [D, 8]

Descending to the first child of 3: node A
Added A's sibling B to the queue.
The queue is now: [D, 8, B]
Output leaf: A


Queue is not empty: [D, 8, B]
Added D's sibling 11 to the queue.
The queue is now: [11, 8, B]
Output leaf: D


Queue is not empty: [11, 8, B]
11 has no more siblings.

Descending to the first child of 11: node F
Added F's sibling 13 to the queue.
The queue is now: [8, 13, B]
Output leaf: F


Queue is not empty: [8, 13, B]
8 has no more siblings.

Descending to the first child of 8: node E
E has no more siblings.
Output leaf: E


Queue is not empty: [13, B]
13 has no more siblings.

Descending to the first child of 13: node 14
Added 14's sibling 17 to the queue.
The queue is now: [B, 17]

Descending to the first child of 14: node G
Added G's sibling H to the queue.
The queue is now: [B, 17, H]
Output leaf: G


Queue is not empty: [B, 17, H]
Added B's sibling 6 to the queue.
The queue is now: [17, 6, H]
Output leaf: B


Queue is not empty: [17, 6, H]
Added 17's sibling K to the queue.
The queue is now: [6, K, H]

Descending to the first child of 17: node 18
18 has no more siblings.

Descending to the first child of 18: node I
Added I's sibling J to the queue.
The queue is now: [6, K, H, J]
Output leaf: I


Queue is not empty: [6, K, H, J]
6 has no more siblings.

Descending to the first child of 6: node C
C has no more siblings.
Output leaf: C


Queue is not empty: [K, H, J]
K has no more siblings.
Output leaf: K


Queue is not empty: [H, J]
H has no more siblings.
Output leaf: H


Queue is not empty: [J]
J has no more siblings.
Output leaf: J

You can play with a JavaScript implementation by Apass.Jack of this algorithm

The only slowdown for this algorithm is the stable priority queue. Using generic stable priority queue will give you $\mathcal{O}(n \log n)$ total runtime, where $n$ is the size of the tree.

However, it is possible to cut the running time down to $\mathcal{O}(n)$. Note that once we take a node with priority $p$ from the top of the queue, we will then possibly add a node with priority $p$, then descend to the child, then possibly add a node with priority $p+1$ and so on. This gives an idea to implement the priority queue as a linked list:

  1. Each element of the list is a queue of nodes with the same priority.
  2. Top priority is at the head of the list. If we pop last node from the top queue, the head of the list is removed.
  3. When we descend to a child, the (candidate) priority is incremented, so we should move through the list, if necessary.
  4. When we push new node, we either insert new queue into the list, or push the element to existing one.

Here's the states of such a priority queue from the run above (asterisk means current queue for insertion):

Initial:
└─[1] *

After popping node 1 and descending to node 2:
└─[D] *

After descending to node 3:
├─[D]
└─[8] *

After descending to node A:
├─[D]
├─[8]
└─[B] *

Taking D from the top:
├─[8] *
└─[B]

And pushing 11 before [8] because of greater priority.
├─[11] *
├─[8]
└─[B]

Taking 11 from the top and adding 13, which has the same priority as 8:
├─[8, 13] *
└─[B]

Taking 8 from the top:
├─[13] *
└─[B]

Taking 13 from the top:
└─[B] *

Pushing 17 with the same as B priority:
└─[B, 17] *

Added H to after [B, 17] because we descended:
├─[B, 17]
└─[H] *

Took B from the top:
├─[17] *
└─[H]

Added 6:
├─[17, 6] *
└─[H]

Took 17, added K:
├─[6, K] *
└─[H]

Descended to the child:
├─[6, K]
└─[H] *

Added J to a new queue, because we descended:
├─[6, K]
├─[H]
└─[J] *

Exhausting the rest of the queue:
├─[K] *
├─[H]
└─[J]

├─[H] *
└─[J]

└─[J] *
$\endgroup$
9
  • $\begingroup$ I cannot see how this algorithm works. Can you show its step-by-step application on the example provided by OP? $\endgroup$
    – John L.
    Aug 6, 2018 at 18:17
  • $\begingroup$ @Apass.Jack Added sample run. it wasn't clear whether grouping in rounds is required, so it only outputs the leafs in the same order. $\endgroup$ Aug 7, 2018 at 11:09
  • $\begingroup$ Priority queues are an interesting approach for this problem. Since I had limited time on this, I went with the other answer which had a more algorithmic pseudo-code. But I can see how this could also work. Thanks for your answer. $\endgroup$ Aug 27, 2018 at 13:36
  • $\begingroup$ @MadChuckle, this answer is also very elegant. Somehow the author does not bother to offer a simple explanation of the ideas behind his algorithm in plain English, which is simple and direct. Without that, it might not be easy to believe its correctness at the first sight . However, I had also verified that it does work by running an actual implementation. $\endgroup$
    – John L.
    Aug 27, 2018 at 15:45
  • $\begingroup$ @Apass.Jack, thanks for being thorough and implementing this approach too. I agree that this is also elegant as the author correctly identified the question as a priorities of depth problem that is already solved by an existing data structure. AFAIK priority queues have also O(n.log(n)) complexities, so the times could be similar to your zipping method, but an implementation would need more lines I guess in JS unless you use a library of course. $\endgroup$ Aug 29, 2018 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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