Morph MORPH
SIGN IN SIGN UP
TheAlgorithms / JavaScript UNCLAIMED

Algorithms and Data Structures implemented in JavaScript for beginners, following best practices.

0 0 0 JavaScript
Normal View History Raw
Implement BreadthFirstTreeTraversal in JavaScript (#435) * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript
2020-10-12 15:56:01 +08:00
/*
Breadth First Tree Traversal or level order traversal implementation in javascript
Author: @GerardUbuntu
*/
class Node {
constructor (data) {
this.data = data
this.left = null
this.right = null
}
}
class BinaryTree {
constructor () {
this.root = null
}
algorithm: Iterative (and in-place) BFS for binary trees (#1102) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity
2022-09-22 04:54:29 -07:00
breadthFirstIterative () {
refactor: BFS tree algorithms (#1108) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity * refactor out traversal member var .. per earlier discussion w mods also tweaked the tests to achieve 100% coverage
2022-09-25 01:11:00 -07:00
const traversal = []
algorithm: Iterative (and in-place) BFS for binary trees (#1102) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity
2022-09-22 04:54:29 -07:00
if (this.root) {
refactor: BFS tree algorithms (#1108) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity * refactor out traversal member var .. per earlier discussion w mods also tweaked the tests to achieve 100% coverage
2022-09-25 01:11:00 -07:00
traversal.push(this.root)
algorithm: Iterative (and in-place) BFS for binary trees (#1102) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity
2022-09-22 04:54:29 -07:00
}
refactor: BFS tree algorithms (#1108) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity * refactor out traversal member var .. per earlier discussion w mods also tweaked the tests to achieve 100% coverage
2022-09-25 01:11:00 -07:00
for (let i = 0; i < traversal.length; i++) {
const currentNode = traversal[i]
algorithm: Iterative (and in-place) BFS for binary trees (#1102) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity
2022-09-22 04:54:29 -07:00
if (currentNode.left) {
refactor: BFS tree algorithms (#1108) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity * refactor out traversal member var .. per earlier discussion w mods also tweaked the tests to achieve 100% coverage
2022-09-25 01:11:00 -07:00
traversal.push(currentNode.left)
algorithm: Iterative (and in-place) BFS for binary trees (#1102) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity
2022-09-22 04:54:29 -07:00
}
if (currentNode.right) {
refactor: BFS tree algorithms (#1108) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity * refactor out traversal member var .. per earlier discussion w mods also tweaked the tests to achieve 100% coverage
2022-09-25 01:11:00 -07:00
traversal.push(currentNode.right)
algorithm: Iterative (and in-place) BFS for binary trees (#1102) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity
2022-09-22 04:54:29 -07:00
}
refactor: BFS tree algorithms (#1108) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity * refactor out traversal member var .. per earlier discussion w mods also tweaked the tests to achieve 100% coverage
2022-09-25 01:11:00 -07:00
traversal[i] = currentNode.data
algorithm: Iterative (and in-place) BFS for binary trees (#1102) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity
2022-09-22 04:54:29 -07:00
}
refactor: BFS tree algorithms (#1108) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity * refactor out traversal member var .. per earlier discussion w mods also tweaked the tests to achieve 100% coverage
2022-09-25 01:11:00 -07:00
return traversal
algorithm: Iterative (and in-place) BFS for binary trees (#1102) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity
2022-09-22 04:54:29 -07:00
}
breadthFirstRecursive () {
refactor: BFS tree algorithms (#1108) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity * refactor out traversal member var .. per earlier discussion w mods also tweaked the tests to achieve 100% coverage
2022-09-25 01:11:00 -07:00
const traversal = []
Implement BreadthFirstTreeTraversal in JavaScript (#435) * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript
2020-10-12 15:56:01 +08:00
const h = this.getHeight(this.root)
merge: Let traverseLevel return early if node is null (#878)
2022-01-24 17:43:48 +08:00
for (let i = 0; i !== h; i++) {
refactor: BFS tree algorithms (#1108) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity * refactor out traversal member var .. per earlier discussion w mods also tweaked the tests to achieve 100% coverage
2022-09-25 01:11:00 -07:00
this.traverseLevel(this.root, i, traversal)
Implement BreadthFirstTreeTraversal in JavaScript (#435) * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript
2020-10-12 15:56:01 +08:00
}
refactor: BFS tree algorithms (#1108) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity * refactor out traversal member var .. per earlier discussion w mods also tweaked the tests to achieve 100% coverage
2022-09-25 01:11:00 -07:00
return traversal
Implement BreadthFirstTreeTraversal in JavaScript (#435) * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript
2020-10-12 15:56:01 +08:00
}
fixed some spellings
2021-10-05 12:49:23 +05:30
// Computing the height of the tree
Implement BreadthFirstTreeTraversal in JavaScript (#435) * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript
2020-10-12 15:56:01 +08:00
getHeight (node) {
merge: Let traverseLevel return early if node is null (#878)
2022-01-24 17:43:48 +08:00
if (node === null) {
Implement BreadthFirstTreeTraversal in JavaScript (#435) * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript
2020-10-12 15:56:01 +08:00
return 0
}
merge: Let traverseLevel return early if node is null (#878)
2022-01-24 17:43:48 +08:00
const lheight = this.getHeight(node.left)
const rheight = this.getHeight(node.right)
return lheight > rheight ? lheight + 1 : rheight + 1
Implement BreadthFirstTreeTraversal in JavaScript (#435) * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript
2020-10-12 15:56:01 +08:00
}
refactor: BFS tree algorithms (#1108) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity * refactor out traversal member var .. per earlier discussion w mods also tweaked the tests to achieve 100% coverage
2022-09-25 01:11:00 -07:00
traverseLevel (node, levelRemaining, traversal) {
merge: Let traverseLevel return early if node is null (#878)
2022-01-24 17:43:48 +08:00
if (node === null) {
return
}
if (levelRemaining === 0) {
refactor: BFS tree algorithms (#1108) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity * refactor out traversal member var .. per earlier discussion w mods also tweaked the tests to achieve 100% coverage
2022-09-25 01:11:00 -07:00
traversal.push(node.data)
Implement BreadthFirstTreeTraversal in JavaScript (#435) * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript
2020-10-12 15:56:01 +08:00
} else {
refactor: BFS tree algorithms (#1108) * Bugfix AVLTree comparator The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test. I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes. * 100% jest code coverage Added a couple of extra elements to the original test tree, and then removed elements in an order such that all previously uncovered branches of code are now covered. Also added an emptyTree structure to test some additional (trivial) base cases. * standard style fix missed this from my previous commit * Iterative & in-place BFS An iterative analog to the traditional recursive breadth-first-search algorithm for binary trees. This in-place solution uses the pre-existing "traversal" array for both tracking the algorithm as well as storing the result. Also tweaked old code by resetting the traversal array each time the tree is traversed (otherwise you're only allowed to traverse a tree once which doesn't seem correct even with a single traversal function). * Update BreadthFirstTreeTraversal.js got rid of unnecessary currentSize added currentNode for clarity * refactor out traversal member var .. per earlier discussion w mods also tweaked the tests to achieve 100% coverage
2022-09-25 01:11:00 -07:00
this.traverseLevel(node.left, levelRemaining - 1, traversal)
this.traverseLevel(node.right, levelRemaining - 1, traversal)
Implement BreadthFirstTreeTraversal in JavaScript (#435) * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript * Implement BreadthFirstTreeTraversal in JavaScript
2020-10-12 15:56:01 +08:00
}
}
}
Breadth FIrst Tree Traversal : Convert live test into Jest test.
2021-10-11 14:48:06 +02:00
export { BinaryTree, Node }
Reference in New Issue Copy Permalink