91 lines
2.6 KiB
JavaScript
91 lines
2.6 KiB
JavaScript
// https://www.freecodecamp.org/learn/coding-interview-prep/data-structures/use-depth-first-search-in-a-binary-search-tree
|
|
|
|
var displayTree = (tree) => console.log(JSON.stringify(tree, null, 2));
|
|
function Node(value) {
|
|
this.value = value;
|
|
this.left = null;
|
|
this.right = null;
|
|
}
|
|
function BinarySearchTree() {
|
|
this.root = null;
|
|
// Only change code below this line
|
|
this.inorder = () => {
|
|
if (this.root === null) {
|
|
return null;
|
|
}
|
|
const values = [];
|
|
const stack = [{ node: this.root, stage: "left" }];
|
|
while (stack.length) {
|
|
const { node, stage } = stack[stack.length - 1];
|
|
if (stage === "left") {
|
|
stack[stack.length - 1].stage = "node";
|
|
if (node.left !== null) {
|
|
stack.push({ node: node.left, stage: "left" });
|
|
}
|
|
} else if (stage === "node") {
|
|
stack[stack.length - 1].stage = "right";
|
|
values.push(node.value);
|
|
} else if (stage === "right") {
|
|
stack.pop();
|
|
if (node.right !== null) {
|
|
stack.push({ node: node.right, stage: "left" });
|
|
}
|
|
}
|
|
}
|
|
return values;
|
|
};
|
|
|
|
this.preorder = () => {
|
|
if (this.root === null) {
|
|
return null;
|
|
}
|
|
const values = [];
|
|
const stack = [{ node: this.root, stage: "node" }];
|
|
while (stack.length) {
|
|
const { node, stage } = stack[stack.length - 1];
|
|
if (stage === "node") {
|
|
stack[stack.length - 1].stage = "left";
|
|
values.push(node.value);
|
|
} else if (stage === "left") {
|
|
stack[stack.length - 1].stage = "right";
|
|
if (node.left !== null) {
|
|
stack.push({ node: node.left, stage: "node" });
|
|
}
|
|
} else if (stage === "right") {
|
|
stack.pop();
|
|
if (node.right !== null) {
|
|
stack.push({ node: node.right, stage: "node" });
|
|
}
|
|
}
|
|
}
|
|
return values;
|
|
};
|
|
|
|
this.postorder = () => {
|
|
if (this.root === null) {
|
|
return null;
|
|
}
|
|
const values = [];
|
|
const stack = [{ node: this.root, stage: "left" }];
|
|
while (stack.length) {
|
|
const { node, stage } = stack[stack.length - 1];
|
|
if (stage === "left") {
|
|
stack[stack.length - 1].stage = "right";
|
|
if (node.left !== null) {
|
|
stack.push({ node: node.left, stage: "left" });
|
|
}
|
|
} else if (stage === "right") {
|
|
stack[stack.length - 1].stage = "node";
|
|
if (node.right !== null) {
|
|
stack.push({ node: node.right, stage: "left" });
|
|
}
|
|
} else if (stage === "node") {
|
|
stack.pop();
|
|
values.push(node.value);
|
|
}
|
|
}
|
|
return values;
|
|
};
|
|
// Only change code above this line
|
|
}
|