{"size": 3353, "ext": "js", "max_stars_repo_path": "javascript/code-challenges/tree/tree.js", "max_stars_repo_name": "Vektur/data-structures-and-algorithms", "max_stars_repo_stars_event_min_datetime": null, "max_stars_repo_stars_event_max_datetime": null, "max_issues_repo_path": "javascript/code-challenges/tree/tree.js", "max_issues_repo_name": "Vektur/data-structures-and-algorithms", "max_issues_repo_issues_event_min_datetime": "2020-12-17T21:43:24.000Z", "max_issues_repo_issues_event_max_datetime": "2021-03-24T22:07:17.000Z", "max_forks_repo_path": "javascript/code-challenges/tree/tree.js", "max_forks_repo_name": "Vektur/data-structures-and-algorithms", "max_forks_repo_forks_event_min_datetime": null, "max_forks_repo_forks_event_max_datetime": null}
{"max_stars_count": null, "max_issues_count": 7, "max_forks_count": null, "avg_line_length": 18.4230769231, "max_line_length": 75, "alphanum_fraction": 0.4903071876}
'use strict';
const Node = require('./node.js');

class BinaryTree {

  constructor() {
    this.root = null;
  }

  insert(val) {

    const node = this.root;
    if ( node === null ) {
      this.root = new Node(val);
      return;
    }

    let _insert = (node) => {

      // Left is less  (< val)  ()< val  ()< val  ()< val
      if ( val < node.val ) {
        // If no left node, create a new node for it, with the current val
        if ( node.left === null ) {
          node.left = new Node(val);
          return;
        }
        // Otherwise,
        else if ( node.left !== null ) {
          return _insert(node.left);
        }
      }
      // Right is might (> val)
      else if ( val >= node.val ) {
        // If no right node, create a new node for it, with the current val
        if ( node.right === null ) {
          node.right = new Node(val);
          return;
        }
        // Otherwise,
        else if ( node.right !== null ) {
          return _insert(node.right);
        }
      }
      else {
        return null;
      }
    };

    _insert(node);

  }

  preOrder() {
    let nodes = [];

    let traverse = (node) => {
      nodes.push(node.val);
      if (node.left) { traverse(node.left); }
      if (node.right) { traverse(node.right); }
    };

    traverse(this.root);

    return nodes;
  }

  inOrder() {

    let nodes = [];

    let traverse = (node) => {
      if (node.left) { traverse(node.left); }
      nodes.push(node.val);
      if (node.right) { traverse(node.right); }
    };

    // Start the process
    traverse(this.root);

    return nodes;

  }

  postOrder() {

    let nodes = [];
    let traverse = (node) => {
      if (node.left) { traverse(node.left); }
      if (node.right) { traverse(node.right); }
      nodes.push(node.val);
    };

    traverse(this.root);

    return nodes;
  }

  maxVal() {
    let max = 0;
    let trek = (node) => {
      max = node.val > max ? node.val : max;
      if (node.left) { trek(node.left); }
      if (node.right) { trek(node.right); }
    };

    trek(this.root);

    return max;
  }

  breadthFirst() {
    let nodes = [];
    let queue = [];

    queue.push(this.root); 

    while(queue.length) {
    
      let currentNode = queue.shift(); 

      nodes.push(currentNode.val);

      if(currentNode.left) { queue.push(currentNode.left); }
      if(currentNode.right) { queue.push(currentNode.right); }
    }
    return nodes;
  }

}

class BST extends BinaryTree {
  add(val) {
    let newNode = new Node(val);

    if (!this.root) {
      this.root = newNode
      return 'added';
    }

    const trek = (node) => {
      if (val < node.val) {
        if (!node.left) {
          node.left = newNode;
          return 'added';
        }
        trek(node.left);
      }

      if (val > node.val) {
        if (!node.right) {
          node.right = newNode;
          return 'added';
        }
        trek(node.right);
      }
    };
    trek(this.root);
  }

  contains(val) {
    let nodeVal = this.root;
    while (nodeVal) {
      if (nodeVal.val === val) return true;

      if (val < nodeVal.val && nodeVal.left) {
        nodeVal = nodeVal.left;
      }

      if (val > nodeVal.val && nodeVal.right) {
        nodeVal = nodeVal.right;
      }

      else {
        return false;
      }
    }
  }
}

module.exports = BST;

