// 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
}