How to create a reference implementation for a Tree in JavaScript

Here is one reference implementation for a tree, binary tree and relevant traversals:

TreeTry in REPL
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
function Tree(data) {
this.data = data;
this.children = [];
}
Tree.prototype.addChild = function(data) {
const child = new Tree(data);
this.children.push(child);
};
Tree.prototype.contains = function(target) {
if (this.data === target) {
return true;
}
for (let i = 0; i < this.children.length; i++) {
const child = this.children[i];
if (child.contains(target)) {
return true;
}
}
return false;
};
function inOrderTraversal(tree, callback = identity, array = []) {
if (tree) {
inOrderTraversal(tree.left, callback, array);
visit(array, tree.data);
inOrderTraversal(tree.right, callback,array);
}
return array.map(callback);
}
function preOrderTraversal(tree, callback = identity, array = []) {
if (tree) {
visit(array, tree.data);
preOrderTraversal(tree.left, callback, array);
preOrderTraversal(tree.right, callback, array);
}
return array.map(callback);
}
function postOrderTraversal(tree, callback = identity, array = []) {
if (tree) {
postOrderTraversal(tree.left, callback, array);
postOrderTraversal(tree.right, callback, array);
visit(array, tree.data);
}
return array.map(callback);
}
function visit(array, data) {
array.push(data);
}
function identity(element) {
return element
}
function BinaryTree(data) {
this.data = data;
this.left = null;
this.right = null;
}
BinaryTree.prototype.addChild = function(data) {
const child = new BinaryTree(data);
if (!this.left) {
this.left = child;
} else if (!this.right) {
this.right = child;
} else {
// we could handle adding grandchildren from the root tree here.
}
}
BinaryTree.prototype.contains = function(target, containsTarget = false) {
if (this.data === target) {
return true;
}
if (this.left && this.left.contains(target, containsTarget)) {
containsTarget = true;
} else if (this.right && this.right.contains(target, containsTarget)) {
containsTarget = true;
}
return containsTarget;
};

Tests can be found at REPL.it