Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A RRR-TL Traversal is an hierarchical algorithm that gives each sub-tree equal priority among its siblings with respect to its parent recursively
// ====================================================================
// RECURSIVE ROUND ROBIN (RRR) TREE LEAF TRAVERSAL ALGORITHM (JS ES6+)
// METHOD IDEA: Cagil Seker [ÇAĞIL ŞEKER] (MadChuckle) - cagils@gmail.com
// SAMPLE ALGORITHM: Apass.Jack (https://cs.stackexchange.com/users/91753/apass-jack)
// ====================================================================
// This is a gist for my (MadChuckle) question at StackOverflow
// Link: 'https://cs.stackexchange.com/questions/95951/is-there-a-name-and-efficient-algorithm-for-this-tree-traversal-method'
//
// This is based on the the pseudo code (and later an implementation) from Apass.Jack
//
// *****************************************************************************
// * A RRR-TL Traversal is an hierarchical algorithm that gives each sub-tree *
// * equal priority among its siblings with respect to its parent recursively *
// * Refer to the linked SO question above for more information. *
// *****************************************************************************
//
// INPUT: [[['A', 'B', ['C']], ['E']], 'D', ['F', [['G', 'H'], [['I', 'J']], 'K']]]
// OUTPUT: ["A","D","F","E","G","B","I","C","K","H","J"]
let myTree = [[['A', 'B', ['C']], ['E']], 'D', ['F', [['G', 'H'], [['I', 'J']], 'K']]]
let result = rrrTraversal(myTree)
console.log(JSON.stringify(result))
// procedure rrrTraversal(rootedTree):
function rrrTraversal(t) {
if (!Array.isArray(t)) {
return [t]
}
// Merge a parent with its child as a minor performance improvement.
if (t.length == 1) {
return rrrTraversal(t[0])
}
let ll = [] // ll := an empty list of lists
// foreach subtree s of rootedTree from left to right:
t.forEach (s => {
let ss = rrrTraversal(s)
ll.push(ss) //push ss to the back of ll
})
return zip(ll)
}
// procedure zip(listOflists):
function zip(ll) {
let zipped = []
// while listOflists is not empty:
while (ll.length) {
let toRemove = [] // indices to be removed
// foreach list li in listOflists from front to end:
for (let i = 0; i < ll.length; i++) {
let li = ll[i]
if (!li.length) { // if li is empty:
toRemove.unshift(i) // add index to the beginning of toRemove
} else {
let fi = li.splice(0, 1)[0] // remove the first item from li and hold it
zipped.push(fi) // push that first item to the back of the zipped
}
}
toRemove.forEach(index => ll.splice(index, 1))
}
return zipped
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.