Trees and Graphs (with JavaScript examples)

TL;DR: Trees and graphs are powerful non-linear data structures that model hierarchical relationships and interconnected networks, respectively. Unlike linear structures, they offer flexible ways to represent complex data, forming the basis for many advanced algorithms. In this post, you’ll learn:

• Trees: how to build different types of trees (binary, binary search trees), insert/delete nodes, and perform various traversals (pre-order, in-order, post-order, BFS).
• Graphs: how to represent graphs (adjacency matrix, adjacency list), implement common traversals (BFS, DFS), and understand their applications. Every concept comes with concise JavaScript examples to illustrate real-world usage and performance considerations.

Looking for coding exercises? Check out my challenges page for hands-on problems to test your understanding of these structures.

Why Non-Linear Data Structures Matter

Modern JavaScript applications often deal with data that isn't naturally linear. Think about file systems, social networks, or mapping applications. These scenarios demand data structures that can efficiently represent relationships and connections that branch or interlink. Trees and graphs are perfectly suited for these challenges because they:

• Model Complex Relationships: They allow for one-to-many (trees) or many-to-many (graphs) relationships, crucial for representing intricate data.
• Enable Efficient Searching and Pathfinding: Algorithms built on trees and graphs can find specific data points or the shortest path between two points rapidly.
• Form the Basis for Advanced Algorithms: Many complex problems in computer science, from AI to network routing, rely on tree and graph theory.

Below, we’ll explore each structure, discuss its use cases, and provide idiomatic JavaScript implementations.

1. Trees

A tree is a hierarchical data structure consisting of nodes, where each node has a value and zero or more child nodes. Unlike linked lists, nodes can have multiple "next" references (children). Trees are commonly used to represent file systems, organization charts, and parse trees in compilers.

1.1. Basic Tree Terminology

• Root: The topmost node of a tree.
• Child: A node directly connected to another node when moving away from the Root.
• Parent: The converse notion of a child.
• Siblings: Nodes that share the same parent.
• Leaf: A node with no children.
• Edge: The connection between two nodes.
• Path: A sequence of nodes and edges connecting one node to another.
• Height: The length of the longest path from a node to a leaf. The height of a tree is the height of its root.
• Depth: The length of the path from the root to a node.

1.2. Binary Trees

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.

1.2.1. TreeNode Class

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

1.2.2. Binary Search Trees (BST)

A Binary Search Tree (BST) is a special type of binary tree where for every node, all values in its left subtree are less than its value, and all values in its right subtree are greater than its value. This property makes searching, insertion, and deletion highly efficient (on average O(log n)).

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

  // Insert a value into the BST
  insert(value) {
    const newNode = new TreeNode(value)
    if (this.root === null) {
      this.root = newNode
      return this
    }
    let current = this.root
    while (true) {
      if (value === current.value) return undefined // Handle duplicates (or choose to allow them)
      if (value < current.value) {
        if (current.left === null) {
          current.left = newNode
          return this
        }
        current = current.left
      } else {
        if (current.right === null) {
          current.right = newNode
          return this
        }
        current = current.right
      }
    }
  }

  // Find a value in the BST
  find(value) {
    if (!this.root) return false
    let current = this.root
    let found = false
    while (current && !found) {
      if (value < current.value) {
        current = current.left
      } else if (value > current.value) {
        current = current.right
      } else {
        found = true
      }
    }
    return found
  }

  // BST Traversal: Breadth-First Search (BFS)
  BFS() {
    let node = this.root
    let queue = []
    let visited = []
    queue.push(node)

    while (queue.length) {
      node = queue.shift()
      visited.push(node.value)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
    return visited
  }

  // BST Traversal: Depth-First Search (DFS) - Pre-order
  DFSPreOrder() {
    let visited = []
    function traverse(node) {
      visited.push(node.value)
      if (node.left) traverse(node.left)
      if (node.right) traverse(node.right)
    }
    traverse(this.root)
    return visited
  }

  // BST Traversal: Depth-First Search (DFS) - Post-order
  DFSPostOrder() {
    let visited = []
    function traverse(node) {
      if (node.left) traverse(node.left)
      if (node.right) traverse(node.right)
      visited.push(node.value)
    }
    traverse(this.root)
    return visited
  }

  // BST Traversal: Depth-First Search (DFS) - In-order
  DFSInOrder() {
    let visited = []
    function traverse(node) {
      if (node.left) traverse(node.left)
      visited.push(node.value)
      if (node.right) traverse(node.right)
    }
    traverse(this.root)
    return visited
  }

  // Helper for deleting a node (simplified for brevity, often more complex)
  // For a full implementation, consider cases for 0, 1, or 2 children.
  // This example focuses on understanding the concept rather than a production-ready delete.
  delete(value) {
    this.root = this._deleteNode(this.root, value)
  }

  _deleteNode(node, value) {
    if (node === null) {
      return null
    }
    if (value < node.value) {
      node.left = this._deleteNode(node.left, value)
    } else if (value > node.value) {
      node.right = this._deleteNode(node.right, value)
    } else {
      // Node with only one child or no child
      if (node.left === null) {
        return node.right
      } else if (node.right === null) {
        return node.left
      }
      // Node with two children: Get the in-order successor (smallest in the right subtree)
      node.value = this._minValue(node.right)
      // Delete the in-order successor
      node.right = this._deleteNode(node.right, node.value)
    }
    return node
  }

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

1.2.3. Usage Example (BST)

const bst = new BinarySearchTree()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(2)
bst.insert(7)
bst.insert(12)
bst.insert(17)

console.log('BFS Traversal:', bst.BFS()) // [10, 5, 15, 2, 7, 12, 17]
console.log('DFS Pre-order Traversal:', bst.DFSPreOrder()) // [10, 5, 2, 7, 15, 12, 17]
console.log('DFS In-order Traversal:', bst.DFSInOrder()) // [2, 5, 7, 10, 12, 15, 17] (Sorted!)
console.log('DFS Post-order Traversal:', bst.DFSPostOrder()) // [2, 7, 5, 12, 17, 15, 10]

console.log('Find 7:', bst.find(7)) // true
console.log('Find 99:', bst.find(99)) // false

bst.delete(10) // Deleting the root (example of usage)
console.log('BFS after deleting 10:', bst.BFS()) // Will vary based on delete implementation, but should be valid BST

When to Use Trees

• Hierarchical Data: File systems, XML/HTML document structures (DOM), organization charts.
• Efficient Searching and Sorting: Binary Search Trees are optimized for quick lookups, insertions, and deletions, and in-order traversal yields sorted data.
• Parsing and Compilers: Representing syntax trees of programming languages.
• Decision Making: Decision trees in machine learning.

2. Graphs

A graph is a non-linear data structure consisting of a set of nodes (vertices) and a set of connections (edges) between them. Graphs can represent relationships where elements are connected in a non-hierarchical fashion, like social networks, road maps, or computer networks.

2.1. Graph Terminology

• Vertex (Node): A fundamental entity of which the graph is formed.
• Edge (Arc/Link): A connection between two vertices.
• Adjacency: Two vertices are adjacent if they are connected by an edge.
• Degree: The number of edges connected to a vertex.
• Path: A sequence of distinct vertices connected by edges.
• Cycle: A path that starts and ends at the same vertex.
• Directed Graph (Digraph): Edges have a direction (e.g., one-way streets).
• Undirected Graph: Edges have no direction (e.g., two-way streets).
• Weighted Graph: Edges have associated values (weights) (e.g., distance, cost).

2.2. Graph Representations

There are two primary ways to represent a graph:

2.2.1. Adjacency Matrix

An adjacency matrix is a square matrix (rows and columns equal to the number of vertices) where an entry matrix[i][j] is 1 if there is an edge from vertex i to vertex j, and 0 otherwise. For weighted graphs, it stores the weight.

Pros: O(1) to check if an edge exists. Cons: High memory usage ($O(V^2)$), especially for sparse graphs (few edges).

2.2.2. Adjacency List

An adjacency list is an array (or hash map) where each index (or key) represents a vertex, and the value at that index (or key) is a list of its adjacent vertices.

Pros: Memory efficient for sparse graphs ($O(V + E)$), efficient for iterating over neighbors. Cons: O(degree(V)) to check if an edge exists between two specific vertices.

// We'll use Adjacency List for our examples as it's generally more common
// and memory-efficient for real-world graphs.
class Graph {
  constructor() {
    this.adjacencyList = {} // Using a hash map for easy vertex lookup
  }

  // Add a vertex to the graph
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = []
    }
  }

  // Add an edge between two vertices
  addEdge(vertex1, vertex2) {
    if (this.adjacencyList[vertex1] && this.adjacencyList[vertex2]) {
      this.adjacencyList[vertex1].push(vertex2)
      this.adjacencyList[vertex2].push(vertex1) // For undirected graph
    } else {
      console.warn(`One or both vertices (${vertex1}, ${vertex2}) not found.`)
    }
  }

  // Remove an edge between two vertices
  removeEdge(vertex1, vertex2) {
    if (this.adjacencyList[vertex1] && this.adjacencyList[vertex2]) {
      this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
        (v) => v !== vertex2,
      )
      this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
        (v) => v !== vertex1,
      )
    }
  }

  // Remove a vertex and all its associated edges
  removeVertex(vertex) {
    if (!this.adjacencyList[vertex]) return
    for (let adjacentVertex of this.adjacencyList[vertex]) {
      this.removeEdge(vertex, adjacentVertex) // Remove edges connected to this vertex
    }
    delete this.adjacencyList[vertex]
  }

  // Graph Traversal: Breadth-First Search (BFS)
  // Explores neighbor nodes at the current depth level before moving on to nodes at the next depth level.
  BFS(start) {
    const queue = [start]
    const visited = {}
    const result = []
    visited[start] = true

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

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

  // Graph Traversal: Depth-First Search (DFS) - Recursive
  // Explores as far as possible along each branch before backtracking.
  DFS(start) {
    const result = []
    const visited = {}
    const adjacencyList = this.adjacencyList // Reference to 'this' for nested function

    ;(function dfsRecursive(vertex) {
      if (!vertex) return null
      visited[vertex] = true
      result.push(vertex)

      adjacencyList[vertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          dfsRecursive(neighbor)
        }
      })
    })(start) // Immediately invoke with start vertex

    return result
  }

  // DFS - Iterative (using a stack)
  DFSIterative(start) {
    const stack = [start]
    const result = []
    const visited = {}
    visited[start] = true

    while (stack.length) {
      let currentVertex = stack.pop()
      result.push(currentVertex)

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

2.2.3. Usage Example (Graph)

const graph = new Graph()
graph.addVertex('A')
graph.addVertex('B')
graph.addVertex('C')
graph.addVertex('D')
graph.addVertex('E')
graph.addVertex('F')

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

/*
   A -- B -- D
   |    |    |
   C -- E -- F
*/

console.log('Graph Adjacency List:', graph.adjacencyList)
// Expected: { A: ['B', 'C'], B: ['A', 'D'], C: ['A', 'E'], D: ['B', 'E', 'F'], E: ['C', 'D', 'F'], F: ['D', 'E'] }

console.log('BFS from A:', graph.BFS('A')) // [ 'A', 'B', 'C', 'D', 'E', 'F' ]
console.log('DFS from A (recursive):', graph.DFS('A')) // [ 'A', 'B', 'D', 'E', 'C', 'F' ] (order may vary slightly depending on adjacency list iteration)
console.log('DFS from A (iterative):', graph.DFSIterative('A')) // [ 'A', 'C', 'E', 'F', 'D', 'B' ] (order may vary)

graph.removeEdge('D', 'F')
console.log('Graph after removing D-F edge:', graph.adjacencyList)

graph.removeVertex('E')
console.log('Graph after removing E vertex:', graph.adjacencyList)

When to Use Graphs

• Social Networks: Representing users and their connections.
• Mapping and Navigation: Roads, cities, and routes in GPS systems.
• Network Routing: Data flow in computer networks.
• Dependencies: Task scheduling or project management where tasks depend on others.
• State Machines: Modeling transitions between states in a system.

3. Comparing Trees vs. Graphs

4. Putting It All Together

1. When to pick a Tree • Your data has a natural hierarchy (e.g. organizational charts, nested comments). • You need ordered data via in-order traversal (e.g. sorted outputs). • You want guaranteed acyclic structure.

2. When to pick a Graph • Your entities can have arbitrary relationships (e.g. social-media friends). • You need to model cycles or bi-directional links (e.g. road networks). • You’re solving shortest-path or connectivity problems.

5. Next Steps & Challenges

• Hands-On Exercises

  1. Build a family-tree component in vanilla JS: support add/remove members and render with BFS ordering.
  2. Implement Dijkstra’s algorithm on a weighted graph class to find the shortest path in a simple map.
  3. Modify the BST to allow duplicate values by tracking a count per node.

• Further Reading

  • MDN: Tree traversal algorithms
  • Graph theory basics on GeeksforGeeks

• Quiz Yourself

  • When would an AVL or Red-Black tree be preferable over a plain BST?
  • How does memory usage differ between adjacency lists and matrices for sparse vs. dense graphs?

Conclusion

Trees and graphs unlock powerful ways to model non-linear relationships in JavaScript. Whether you’re managing nested UI components, rendering hierarchical data, or calculating optimal routes, understanding these structures—and the algorithms that traverse them—is key to building performant, maintainable applications.

Feel free to revisit the [code samples above], adapt them to your projects, and tackle the challenges on my challenges page to solidify your grasp. Happy coding!