function Node(val) {
return {
val,
left: null,
right: null
};
}
function Tree() {
return {
root: null,
addLeft(val, root) {
const newNode = Node(val);
root.left = newNode;
return newNode;
},
addRight(val, root) {
const newNode = Node(val);
root.right = newNode;
return newNode;
},
levelOrder(root, visitFn) {
const helper = (node, visitFn) => {
if (node === null) {
return;
}
const q = new Queue();
q.push(node);
while (!q.isEmpty()) {
const current = q.peak();
visitFn(current.val);
current.left && q.push(current.left);
current.right && q.push(current.right);
q.pop();
}
};
helper(root, visitFn);
}
};
}
function Queue() {
return {
nodes: [],
push(val) {
this.nodes.push(val); // O(1)
},
pop() {
const [first, ...rest] = this.nodes;
this.nodes = rest;
return first;
},
peak() {
return this.isEmpty() ? null : this.nodes[0];
},
isEmpty() {
return this.nodes.length === 0;
}
};
}
/**
20
14 28
10 15 24 32
4 11 21
*/
const tree = new Tree();
const n1 = Node(20);
tree.root = n1;
const n2 = tree.addLeft(14, n1);
const n3 = tree.addRight(28, n1);
const n4 = tree.addLeft(10, n2);
tree.addRight(15, n2);
const n5 = tree.addLeft(24, n3);
tree.addRight(32, n3);
tree.addLeft(4, n4);
tree.addRight(11, n4);
tree.addLeft(21, n5);
tree.levelOrder(tree.root, x => console.log(x));
//20,14,28,10,15,24,32,4,11,21