-
Notifications
You must be signed in to change notification settings - Fork 0
/
BreadthFirstTreeTraversal.js
70 lines (63 loc) · 1.53 KB
/
BreadthFirstTreeTraversal.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
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
this.traversal = []
}
breadthFirstIterative () {
this.traversal = []
if (this.root) {
this.traversal.push(this.root)
}
for (let i = 0; i < this.traversal.length; i++) {
const currentNode = this.traversal[i]
if (currentNode.left) {
this.traversal.push(currentNode.left)
}
if (currentNode.right) {
this.traversal.push(currentNode.right)
}
this.traversal[i] = currentNode.data
}
return this.traversal
}
breadthFirstRecursive () {
this.traversal = []
const h = this.getHeight(this.root)
for (let i = 0; i !== h; i++) {
this.traverseLevel(this.root, i)
}
return this.traversal
}
// Computing the height of the tree
getHeight (node) {
if (node === null) {
return 0
}
const lheight = this.getHeight(node.left)
const rheight = this.getHeight(node.right)
return lheight > rheight ? lheight + 1 : rheight + 1
}
traverseLevel (node, levelRemaining) {
if (node === null) {
return
}
if (levelRemaining === 0) {
this.traversal.push(node.data)
} else {
this.traverseLevel(node.left, levelRemaining - 1)
this.traverseLevel(node.right, levelRemaining - 1)
}
}
}
export { BinaryTree, Node }