data structures & algorithms with javascript

graph.js

class Vertex {
  constructor (label, wasVisited) {
    this.label = label;
    this.wasVisited = wasVisited;
  }
}

class Graph {
  constructor (v) {
    this.vertices = v;
    this.edges = 0;
    this.adj = [];
    this.marked = [];

    for (let i = 0; i < this.vertices; ++i) {
      this.adj.push([]);
      this.marked.push(false);
    }
  }

  addEdge (v, w) {
    this.adj[v].push(w);
    this.adj[w].push(v);
    this.edges++;
  }

  showGraph () {
    for (let i = 0; i < this.vertices; ++i) {
      let print = `${i} -> `;
      for (let j = 0; j < this.vertices; ++j) {
        if (this.adj[i][j] !== undefined) {
          print += `${this.adj[i][j]} `;
        }
      }
      console.log(print);
    }
  }

  dfs (v) {
    this.marked[v] = true;
    if (this.adj[v] !== undefined) {
      console.log(`Visited vertex: ${v}`);
    }
    this.adj[v].map(w => !this.marked[w] && this.dfs(w));
  }

  bfs (s) {
    const queue = [];
    this.marked[s] = true;
    queue.push(s);

    while (queue.length) {
      let v = queue.shift();
      if (this.adj[v] !== undefined) {
        console.log(`Visited vertex: ${v}`);
      }
      this.adj[v].map(w => {
        if (!this.marked[w]) {
          this.marked[w] = true;
          queue.push(w);
        }
      });
    }
  }
}

module.exports = { Graph };

link.js

class Node {
  constructor (element) {
    this.element = element;
    this.next = null;
  }
};

class LList {
  constructor () {
    this.head = new Node('head');
  }

  find (item) {
    let currNode = this.head;
    while (currNode.element !== item) currNode = currNode.next;
    return currNode;
  }

  insert (newElement, item) {
    const newNode = new Node(newElement);
    const current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
  }

  display () {
    let currNode = this.head;
    while (!(currNode.next == null)) {
      console.log(currNode.next.element);
      currNode = currNode.next;
    }
  }

  findPrevious (item) {
    let currNode = this.head;
    while (!(currNode === null) && (currNode.next.element !== item))
      currNode = currNode.next;
    return currNode;
  }

  remove (item) {
    const prevNode = this.findPrevious(item);
    prevNode.next && (prevNode.next = prevNode.next.next);
  }
};

module.exports = LList;

tree.js

class Node {
  constructor (data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

class BST {
  constructor () {
    this.root = null;
  }

  insert (data) {
    function __insert__ (node, to) {
      if (to === null) {
        to = node;
      } else if (node.data < to.data) {
        to.left = __insert__(node, to.left);
      } else {
        to.right = __insert__(node, to.right);
      }
      return to;
    }

    this.root = __insert__(new Node(data, null, null), this.root);
  }

  inOrder () {
    const result = [];
    function __inOrder__ (node) {
      if (!(node === null)) {
        __inOrder__(node.left);
        result.push(node.data);
        __inOrder__(node.right);
      }
    }
    __inOrder__(this.root);
    return result;
  }

  preOrder () {
    const result = [];
    function __preOrder__ (node) {
      if (!(node === null)) {
        result.push(node.data);
        __preOrder__(node.left);
        __preOrder__(node.right);
      }
    }
    __preOrder__(this.root);
    return result;
  }

  postOrder () {
    const result = [];
    function __postOrder__ (node) {
      if (!(node === null)) {
        __postOrder__(node.left);
        __postOrder__(node.right);
        result.push(node.data);
      }
    }
    __postOrder__(this.root);
    return result;
  }

  getMin () {
    if (this.root === null) {
      return null;
    } else {
      let current = this.root;
      while (!(current.left === null)) current = current.left;
      return current.data;
    }
  }

  getMax () {
    if (this.root == null) {
      return null;
    } else {
      let current = this.root;
      while (!(current.right === null)) current = current.right;
      return current.data;
    }
  }

  find (data) {
    function __find__ (data, root) {
      if (root !== null) {
        if (root.data === data) {
          return root;
        } else if (data < root.data) {
          return __find__(data, root.left);
        } else {
          return __find__(data, root.right);
        }
      }
      return null;
    }
    return __find__(data, this.root);
  }

  remove (data) {
    function getSmallest (node) {
      if (node.left === null) {
        return node;
      } else {
        return getSmallest(node.left);
      }
    }

    function removeNode(node, data) {
      if (node === null) {
        return null;
      }

      if (data === node.data) {
        // node has no children
        if (node.left === null && node.right === null) {
          return null;
        }
        // node has no left child
        if (node.left === null) {
          return node.right;
        }
        // node has no right child
        if (node.right === null) {
          return node.left
        }
        // node has two children
        const tempNode = getSmallest(node.right);
        return Object.assign({}, node, {
          data: tempNode.data,
          right: removeNode(node.right, tempNode.data)
        });
      } else if (data < node.data) {
        return Object.assign({}, node, {
          left: removeNode(node.left, data)
        });
      } else {
        return Object.assign({}, node, {
          right: removeNode(node.right, data)
        });
      }
    }

    this.root = removeNode(this.root, data);
  }
}

module.exports = { BST };