Data Structures and Algorithms in JavaScript: Hash Table, Tree, Graph

1. Hash Table

JavaScript provides a built-in Map object that implements a hash table. It has methods specifically designed for handling key-value pairs.

|-------------------|
|    Hash Table     |
|-------------------|
|   'apple' : 5     |
|   'banana': 8     |
|   'orange': 12    |
|-------------------|

const hashTableMap = new Map([
  ['apple', 5],
  ['banana', 8],
  ['orange', 12]
])

hashTableMap.set('pineapple', 13)

console.log(hashTableMap.get('pineapple')) // Output: 13

console.log(hashTableMap.size) // Output: 4

hashTableMap.delete('banana')

Implementation without Map. Complexity is O(1) constant time.

class HashTable {
  constructor() {
    // Initialize an empty array to store buckets (each bucket is an array of key-value pairs)
    this.buckets = []
  }

  // Hash function to convert a key into an index
  hash(key) {
    // For simplicity, this is a basic hash function; in practice, a more sophisticated one would be used
    let hashValue = 0
    for (let i = 0; i < key.length; i++) {
      hashValue += key.charCodeAt(i)
    }
    return hashValue % 100 // Modulo to keep the index within a reasonable range (e.g., 100 buckets)
  }

  // Add a key-value pair
  insert(key, value) {
    const index = this.hash(key)
    
    // If the bucket at the calculated index doesn't exist, create it
    if (!this.buckets[index]) {
      this.buckets[index] = []
    }

    // Check if the key already exists in the bucket, and update its value if so
    for (const pair of this.buckets[index]) {
      if (pair[0] === key) {
        pair[1] = value
        return
      }
    }

    // If the key doesn't exist in the bucket, add a new key-value pair
    this.buckets[index].push([key, value])
  }

  // Remove a key-value pair
  remove(key) {
    const index = this.hash(key)
    
    // If the bucket at the calculated index exists, search for the key and remove it
    if (this.buckets[index]) {
      this.buckets[index] = this.buckets[index].filter(pair => pair[0] !== key);
    }
  }

  // Method to get the value associated with a given key
  get(key) {
    const index = this.hash(key)

    // If the bucket at the calculated index exists, search for the key and return its value
    if (this.buckets[index]) {
      for (const pair of this.buckets[index]) {
        if (pair[0] === key) {
          return pair[1]
        }
      }
    }

    // Return undefined if the key is not found
    return undefined
  }
}

// Example usage:
const myHashTable = new HashTable()

// Inserting key-value pairs
myHashTable.insert('apple', 5)
myHashTable.insert('banana', 8)
myHashTable.insert('orange', 12)

// Retrieving values
console.log(myHashTable.get('apple')) // Output: 5
console.log(myHashTable.get('banana')) // Output: 8
console.log(myHashTable.get('grape'))  // Output: undefined (key not present)

// Removing a key-value pair
myHashTable.remove('banana')

// Retrieving values after removal
console.log(myHashTable.get('banana')) // Output: undefined (key removed)

2. Tree

Main elements are root, node/child, edge, and leaf.

• Non-binary Tree

class TreeNode {
  constructor(data) {
    this.data = data
    this.children = []
  }

  addChild(childNode) {
    this.children.push(childNode)
  }
}

class Tree {
  constructor() {
    this.root = null
  }

  addRoot(data) {
    this.root = new TreeNode(data)
  }

  remove(data) {
    if (!this.root) {
      return null
    }

    if (this.root.data === data) {
      this.root = null
      return
    }

    const removeNode = (node, targetData) => {
      node.children = 
        node.children
          .filter((child) => child.data !== targetData)
      node.children.forEach((child) => removeNode(child, targetData))
    }

    removeNode(this.root, data)
  }

  // BFS Traversal
  traverseBFS(callback) {
    if (!this.root) {
      return
    }

    const queue = [this.root]

    while (queue.length > 0) {
      const currentNode = queue.shift()
      callback(currentNode.data)

      currentNode.children.forEach((child) => queue.push(child))
    }
  }

  // DFS Traversal
  traverseDFS(callback, method = 'pre-order') {
    const traversePreOrder = (node) => {
      callback(node.data)
      node.children.forEach(traversePreOrder)
    }

    const traversePostOrder = (node) => {
      node.children.forEach(traversePostOrder)
      callback(node.data)
    }

    if (!this.root) {
      return
    }

    if (method === 'pre-order') {
      traversePreOrder(this.root)
    } else if (method === 'post-order') {
      traversePostOrder(this.root)
    }
  }
}

// Example usage:

// Create a tree
const myTree = new Tree()

// Add a root node
myTree.addRoot("Root Node")

// Add children to the root
const child1 = new TreeNode("Child 1")
const child2 = new TreeNode("Child 2")
myTree.root.addChild(child1)
myTree.root.addChild(child2)

// Add children to Child 1
const child1_1 = new TreeNode("Child 1.1")
const child1_2 = new TreeNode("Child 1.2")
child1.addChild(child1_1)
child1.addChild(child1_2)

// Add a child to Child 2
const child2_1 = new TreeNode("Child 2.1")
child2.addChild(child2_1)

// The resulting tree structure looks like this:
//          Root Node
//         /         \
//    Child 1   Child 2
//   /   |   \       \
//  ... ... ...    Child 2.1

console.log(myTree)

// Remove a child
myTree.remove("Child 1.1")

// Traversal

// Breadth-First Traversal
console.log("Breadth-First Traversal:")
myTree.traverseBFS(data => console.log(data))

// Pre-Order Traversal
console.log("Pre-Order Traversal:")
myTree.traverseDFS(data => console.log(data), 'pre-order')

// Post-Order Traversal
console.log("Post-Order Traversal:")
myTree.traverseDFS(data => console.log(data), 'post-order')

class TreeNode {
  constructor(value) {
    this.value = value
    this.left = null
    this.right = null
  }
}

class BinaryTree {
  constructor() {
    this.root = null
  }

  // Insert
  insert(value) {
    this.root = this._insert(this.root, value);
  }

  _insert(root, value) {
    if (root === null) {
      return new TreeNode(value)
    }

    if (value < root.value) {
      root.left = this._insert(root.left, value)
    } else if (value > root.value) {
      root.right = this._insert(root.right, value)
    }

    return root
  }

  // Remove
  remove(value) {
    this.root = this._remove(this.root, value)
  }

  _remove(root, value) {
    if (root === null) {
      return null
    }

    if (value < root.value) {
      root.left = this._remove(root.left, value)
    } else if (value > root.value) {
      root.right = this._remove(root.right, value)
    } else {
      // Node to be removed found
      if (root.left === null) {
        return root.right
      } else if (root.right === null) {
        return root.left
      }

      // Node with two children, get the inorder successor (smallest in the right subtree)
      root.value = this._minValueNode(root.right)

      // Delete the inorder successor
      root.right = this._remove(root.right, root.value)
    }

    return root
  }

  _minValueNode(node) {
    let current = node
    while (current.left !== null) {
      current = current.left
    }
    return current.value
  }

  // Traverse

  // in-order
  inOrder(node, callback) {
    if (node !== null) {
      this.inOrder(node.left, callback)
      callback(node.value)
      this.inOrder(node.right, callback)
    }
  }

  // pre-order
  preOrder(node, callback) {
    if (node !== null) {
      callback(node.value)
      this.preOrder(node.left, callback)
      this.preOrder(node.right, callback)
    }
  }

  // post-order
  postOrder(node, callback) {
    if (node !== null) {
      this.postOrder(node.left, callback)
      this.postOrder(node.right, callback)
      callback(node.value)
    }
  }

  // Traverse DFS
  traverseDFS(callback, order = 'in-order') {
    if (order === 'in-order') {
      this.inOrder(this.root, callback)
    } else if (order === 'pre-order') {
      this.preOrder(this.root, callback)
    } else if (order === 'post-order') {
      this.postOrder(this.root, callback)
    } else {
      console.error('Invalid traversal order')
    }
  }

  // Traverse BFS
  traverseBFS(callback) {
    if (!this.root) {
      return
    }

    const queue = [this.root]

    while (queue.length > 0) {
      const node = queue.shift()
      callback(node.value)

      if (node.left) {
        queue.push(node.left)
      }
      if (node.right) {
        queue.push(node.right)
      }
    }
  }

  // Contains
  contains(node = this.root, value) {
    if (node === null) {
      return false
    }

    if (value === node.value) {
      return true
    } else if (value < node.value) {
      return this.contains(node.left, value)
    } else {
      return this.contains(node.right, value)
    }
  }
}

// Example usage:
const tree = new BinaryTree()
tree.insert(10)
tree.insert(5)
tree.insert(15)
tree.insert(3)
tree.insert(7)
tree.insert(66)

tree.remove(66)

tree.contains(5)

// Tree visualization:
//     10
//    /  \\
//   5    15
//  / \\ 
// 3   7

console.log("In-order DFS traversal:")
tree.traverseDFS((value) => console.log(value), "in-order") // 3, 5, 7, 10, 15

console.log("\nPre-order DFS traversal:")
tree.traverseDFS((value) => console.log(value), "pre-order") // 10, 5, 3, 7, 15

console.log("\nPost-order DFS traversal:")
tree.traverseDFS((value) => console.log(value), "post-order") // 3, 7, 5, 15, 10

console.log("BFS Traversal:")
tree.traverseBFS((value) => console.log(value)) // 10, 5, 15, 3, 7

3. Graph

Consists of vertices and edges.

class Graph {
  constructor() {
    this.adjacencyList = {}
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = []
    }
  }

  addEdge(vertex1, vertex2) {
    if (!this.adjacencyList[vertex1] || !this.adjacencyList[vertex2]) {
      console.error('Invalid vertex')
      return
    }

    this.adjacencyList[vertex1].push(vertex2)
    this.adjacencyList[vertex2].push(vertex1)
  }

  removeEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(v => v !== vertex2)
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(v => v !== vertex1)
  }

  removeVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      console.error('Vertex does not exist')
      return
    }

    while (this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop()
      this.removeEdge(vertex, adjacentVertex)
    }

    delete this.adjacencyList[vertex]
  }

  traverseBFS(start) {
    const queue = [start]
    const result = []
    const visited = {}
    let currentVertex

    visited[start] = true

    while (queue.length) {
      currentVertex = queue.shift()
      result.push(currentVertex)

      this.adjacencyList[currentVertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          visited[neighbor] = true
          queue.push(neighbor)
        }
      })
    }

    return result
  }

  traverseDFS(start) {
    const result = []
    const visited = {}
    const adjacencyList = this.adjacencyList

    function dfs(vertex) {
      if (!vertex) {
        return null
      }

      visited[vertex] = true
      result.push(vertex)

      adjacencyList[vertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          return dfs(neighbor)
        }
      })
    }

    dfs(start)

    return result
  }

  printGraph() {
    for (const vertex in this.adjacencyList) {
      const neighbors = this.adjacencyList[vertex]
      console.log(`${vertex} -> ${neighbors.join(', ')}`)
    }
  }
}

// Example usage
const graph = new Graph()

graph.addVertex('A')
graph.addVertex('B')
graph.addVertex('C')
graph.addVertex('D')

graph.addEdge('A', 'B')
graph.addEdge('B', 'C')
graph.addEdge('C', 'D')
graph.addEdge('D', 'A')

/*
  Graph Visualization:
  A -------- B
  |          |
  |          |
  D -------- C
*/

graph.printGraph()
// Output:
// A -> B, D
// B -> A, C
// C -> B, D
// D -> C, A

// Traverse
console.log("BFS:", graph.traverseBFS('A')) // Example BFS starting from vertex 'A'
// Output: ['A', 'B', 'D', 'C']
console.log("DFS:", graph.traverseDFS('A')) // Example DFS starting from vertex 'A'
// Output: ['A', 'B', 'C', 'D']

console.log('Before removal:', graph.adjacencyList)
graph.removeVertex('C')
console.log('After removing vertex C:', graph.adjacencyList)
graph.removeEdge('A', 'B')
console.log('After removing edge between A and B:', graph.adjacencyList)

graph.printGraph()
// Output:
// A -> D
// B ->
// D -> A

3.1. Adjacency Matrix

An adjacency matrix is a square matrix used to represent a graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. The size of the matrix is V x V, where V is the number of vertices in the graph.

   A  B  C  D
A  0  1  1  1
B  1  0  1  0
C  1  1  0  1
D  1  0  1  0

const adjacencyMatrix = [
  [0, 1, 1, 1],
  [1, 0, 1, 0],
  [1, 1, 0, 1],
  [1, 0, 1, 0]
]

function addValue(vertex1, vertex2) {
  adjacencyMatrix[vertex1][vertex2] = 1
}

function removeValue(vertex1, vertex2) {
  adjacencyMatrix[vertex1][vertex2] = 0
}

In this example:

• Vertex A is adjacent to B, C, and D.
• Vertex B is adjacent to A, C.
• Vertex C is adjacent to A, B, D.
• Vertex D is adjacent to A, C.

3.2. Adjacency List

An adjacency list is another way to represent a graph. In this representation, each vertex in the graph maintains a list of its neighboring vertices. This is especially useful for sparse graphs, where the number of edges is significantly less than the maximum possible number of edges.

A: B, C, D
B: A, C
C: A, B, D
D: A, C

const adjacencyList = {
  A: ['B', 'C', 'D'],
  B: ['A', 'C'],
  C: ['A', 'B', 'D'],
  D: ['A', 'C']
}

// or using Map
const adjacencyListMap = new Map([
  ['A', ['B', 'C', 'D']],
  ['B', ['A', 'C']],
  ['C', ['A', 'B', 'D']],
  ['D', ['A', 'C']]
])

function addValue(vertex1, vertex2) {
  adjacencyList[vertex1].push(vertex2)
  adjacencyList[vertex2].push(vertex1)
}

function removeValue(vertex1, vertex2) {
  const vertex1Ind = adjacencyList[vertex1].indexOf(vertex2)
  const vertex2Ind = adjacencyList[vertex2].indexOf(vertex1)

  adjacencyList[vertex1].splice(vertex2Ind, 1)
  adjacencyList[vertex2].splice(vertex1Ind, 1)
}