Home/Blog/Programming/Data structures 101: Advanced data structures in JavaScript

Data structures 101: Advanced data structures in JavaScript

15 min read

May 08, 2025

content

JavaScript advanced data structures

Trie data structure

Trie data structure key properties

Trie size based on alphabet count

Implementing tries in JavaScript

Structure of a trie node

How do trie nodes work?

Creating a trie in JavaScript

Trie operations: Insertion, search, and deletion

Self-balancing BST in JavaScript

Common types of self-balancing BSTs

Structure of self-balancing BSTs

Key properties of self-balancing BSTs

Example of a self-balancing BST

Self-balancing BST operations

Self-balancing BST implementation in JavaScript

Segment trees in JavaScript

Key properties of segment trees

Example of a segment tree

Segment tree operations

Implementing segment trees in JavaScript

Binary indexed trees (BIT) in JavaScript

Key properties of binary indexed trees

BIT representation and structure

Example of a binary indexed tree

Binary indexed tree operations

Implementing binary indexed tree in JavaScript

Graph data structures

Key properties of graphs

Graph operations

Graph algorithms

Graph representation in JavaScript

Key advantages of Graphs

Data structures in JavaScript: A Comparison

Wrapping up and next steps

Continue reading about JavaScript

Become a Software Engineer in Months, Not Years

From your first line of code, to your first day on the job — Educative has you covered. Join 2M+ developers learning in-demand programming skills.

Key takeaways:

Space vs. time trade-offs are crucial. Some structures, like tries and segment trees, consume more memory but offer faster query times, whereas binary indexed trees are more space-efficient.
Graphs model real-world relationships, from social networks to shortest-path algorithms; graphs are fundamental in many practical applications.
Self-balancing BSTs maintain efficiency; they ensure $O(\log n)$ operations for insertion, deletion, and search, making them ideal for database indexing and dynamic sets.
Mastering advanced structures gives an interview edge. Many coding interviews focus on these data structures, making them essential for problem-solving and algorithmic thinking.

Have you ever wondered how Google Search delivers results in milliseconds?

Or how can Facebook suggest friends and content with such precision?

Maybe you’ve even been curious about how real-time multiplayer games manage to coordinate thousands of players seamlessly.

The answer lies in advanced data structures.

Data Structures in JavaScript

Data Structures in JavaScript: Visualizations & Exercises

This course provides a quick introduction to Data Structures using JavaScript. The audience for this course is someone who understands the basics of programming in JavaScript (e.g. an undergrad student or a coding boot camp graduate). Data Structures included in this course are Array, Stack, Queue, Dictionary, Set, Hash Table, Linked List, Binary Tree, and Binary Search Tree and Graphs. Each tutorial includes step-by-step visualizations and interactive exercises.

3hrs

Beginner

29 Playgrounds

10 Quizzes

JavaScript advanced data structures#

These are powerful tools that optimize data storage and retrieval, making applications run faster and more efficiently.

If you’re a JavaScript developer looking to level up your problem-solving skills, mastering these structures will give you an edge in technical interviews, algorithm design, and real-world applications.

Let's explore some of the most useful advanced data structures in JavaScript with engaging explanations, code snippets, and visuals.

Trie data structure#

Trie originates from “retrieval” and refers to an ordered tree-like data structure optimized for handling string-related problems. It is also known as a prefix tree or a digital tree and is widely used in applications like dictionary word searches, spell-checking, and search engines for auto-suggestions. It is commonly used for efficient string operations like autocomplete, spell-checking, and word searches.

Trie data structure key properties#

To maintain efficiency, a trie follows certain structural properties:

A trie starts with an empty root node.
Each node typically represents a single character.
Nodes may point to null or have multiple child nodes.
The depth of a trie depends on the length of the longest word stored in it.
Words with a common prefix share the same path in the trie.
The size of a trie depends on the number of words and the number of alphabets (child nodes).

Trie size based on alphabet count#

For example:

There are 26 letters in English, so the trie can have up to 26 unique nodes.
In Bengali, which has 50 letters, the trie can contain up to 50 unique nodes.

Tries are highly efficient for prefix-based searches, auto-completion, and dictionary implementations, making them a fundamental data structure in text processing and search applications.

Implementing tries in JavaScript#

Let’s implement tries in JavaScript.

Structure of a trie node#

Each node in a trie consists of three key components:

char: Stores the character that the node represents.
children[]: An array of pointers to child nodes, with all elements initially set to null.
isEndWord: A boolean flag that indicates whether the node marks the end of a word. It is false by default and is set to true when a word is inserted completely.

How do trie nodes work?#

The root node contains 26 pointers (if storing English words), each representing a letter (A-Z).
These pointers hold either null or a reference to another TrieNode.
Words are stored in a top-to-bottom manner in the trie.
The isEndWord flag is set to true on the last character of a word to mark its completion.

Creating a trie in JavaScript#

To implement a trie in JavaScript, let’s start by defining a TrieNode class to represent a character in a trie, supporting child nodes and end-of-word marking. It demonstrates node creation, marking, and unmarking operations with example outputs.

class TrieNode {
  constructor(char) {
    this.char = char; // Store the character
    this.children = new Array(26).fill(null); // Array of pointers for 26 letters
    this.isEndWord = false; // Marks end of a word
  }
  // Mark this node as the end of a word
  markAsLeaf() {
    this.isEndWord = true;
  }
  // Unmark this node as the end of a word
  unMarkAsLeaf() {
    this.isEndWord = false;
  }
}
// Demonstration of TrieNode Functionality
const nodeA = new TrieNode('A'); // Creating a node for 'A'
const nodeB = new TrieNode('B'); // Creating a node for 'B'
// Mark 'A' as an end of a word
nodeA.markAsLeaf();
// Print Node Details
console.log("Node A:", nodeA);
console.log("Node B:", nodeB);
console.log(`Is 'A' an end of a word? ${nodeA.isEndWord}`); // Output: true
console.log(`Is 'B' an end of a word? ${nodeB.isEndWord}`); // Output: false
// Unmark 'A' as the end of a word
nodeA.unMarkAsLeaf();
console.log(`After unmarking, is 'A' an end of a word? ${nodeA.isEndWord}`); // Output: false

Let’s see if we can do more operations with trie:

Trie operations: Insertion, search, and deletion#

The trie data structure allows for efficient word insertion, searching, and deletion. Here’s how each operation works:

Inserting a word

Traverse from the root, creating nodes if they don’t exist.
Extend existing paths for common prefixes.
Mark the last node as isEndWord = true.
Store words in lowercase and ignore null inputs.

Searching for a word

Traverse the trie using each character.
Return false if a character is missing.
Return true only if the last node is marked as an end word.

Deleting a word

Traverse to the last character.
Remove nodes only if they have no children.
If shared with another word, just unmark isEndWord.

"use strict";
class TrieNode {
  constructor(char = '') {
    this.char = char; // Store character
    this.children = new Array(26).fill(null); // Pointers to child nodes (a-z)
    this.isEndWord = false; // Marks end of a word
  }
}
class Trie {
  constructor() {
    this.root = new TrieNode(); // Root node
  }
  // Get index of a character ('a' -> 0, 'z' -> 25)
  getIndex(char) {
    return char.charCodeAt(0) - "a".charCodeAt(0);
  }
  // Insert a word into the trie
  insert(word) {
    if (!word) return; // Ignore empty words
    let node = this.root;
    for (let char of word.toLowerCase()) {
      let index = this.getIndex(char);
      if (!node.children[index]) node.children[index] = new TrieNode(char); // Create node if missing
      node = node.children[index]; // Move to next node
    }
    node.isEndWord = true; // Mark the last node as end of the word
  }
  // Search for a word in the trie
  search(word) {
    if (!word) return false;
    let node = this.root;
    for (let char of word.toLowerCase()) {
      let index = this.getIndex(char);
      if (!node.children[index]) return false; // If path breaks, word is missing
      node = node.children[index];
    }
    return node.isEndWord; // Return true if last node is marked as end of word
  }
  // Helper function to check if a node has no children
  hasNoChildren(node) {
    return node.children.every(child => child === null);
  }
  // Delete a word recursively
  deleteHelper(node, word, level) {
    if (!node) return false;
    if (level === word.length) {
      if (node.isEndWord) {
        node.isEndWord = false; // Unmark end of word
        return this.hasNoChildren(node); // If no children, delete node
      }
      return false;
    }
    let index = this.getIndex(word[level]);
    let shouldDeleteChild = this.deleteHelper(node.children[index], word, level + 1);
    if (shouldDeleteChild) node.children[index] = null; // Remove reference if child can be deleted
    return this.hasNoChildren(node) && !node.isEndWord;
  }
  // Delete a word from the trie
  delete(word) {
    this.deleteHelper(this.root, word.toLowerCase(), 0);
  }
}
// Example Usage
const trie = new Trie();
trie.insert("apple");
trie.insert("app");
trie.insert("bat");
console.log("Search Results:");
console.log("apple:", trie.search("apple")); // true
console.log("app:", trie.search("app")); // true
console.log("bat:", trie.search("bat")); // true
console.log("banana:", trie.search("banana")); // false
// Delete a word and check again
trie.delete("apple");
console.log("\nAfter Deletion:");
console.log("apple:", trie.search("apple")); // false
console.log("app:", trie.search("app")); // true (since 'app' is still stored)

Trie operations (search, insert, delete) run in $O(n)$ time, where $n$ is the length of the word. While shared prefixes generally make tries efficient and scalable, the worst-case space complexity can be $O(m × n)$ , with $m$ as the average word length and $n$ as the number of words.

Now that we’ve covered how tries handle efficient string operations, let’s focus on self-balancing BSTs—structures that ensure fast, ordered data processing.

Self-balancing BST in JavaScript#

A self-balancing binary search tree is a height-balanced data structure that automatically adjusts (via rotations) during insertions and deletions to maintain a minimal height. This balance is crucial in large-scale databases and indexing systems, ensuring that search, insert, and delete operations remain efficient even as data volume grows.

Common types of self-balancing BSTs#

AVL trees: Strictly balanced with $O(\log n)$ operations.
Red-Black trees: Less strictly balanced but efficient for dynamic sets.
Splay trees: Moves frequently accessed nodes closer to the root.
Treaps: Combines BST properties with heap priorities for randomized balancing.

Structure of self-balancing BSTs#

A self-balancing binary search tree (BST) maintains a structured hierarchy to ensure efficient search, insertion, and deletion operations. The structure follows these key principles:

Root node: This is the topmost node of the tree.
Left subtree: Contains values smaller than the root.
Right subtree: Contains values greater than the root.
Balancing factor: The height difference between left and right subtrees is kept within a defined limit (e.g., AVL trees limit it to at most 1, while other BSTs may use different balancing criteria).
Rotations: If the tree becomes unbalanced, it performs left or right rotations to restore balance while preserving the BST property.

Key properties of self-balancing BSTs#

Height balance: Keeps the tree height as low as possible for efficient traversal.
Efficient operations: Insertions, deletions, and searches operate in $O(\log n)$ time.
Rotations for rebalancing: Restores balance dynamically when the tree structure is modified.
Ordered structure: Ensures that values in the left subtree are smaller for any node and values in the right subtree are greater.

Example of a self-balancing BST#

Before insertion of 50 (Balanced):

This example demonstrates how rotations help maintain balance, ensuring efficient operations in a self-balancing BST. The exact balancing technique depends on the tree type (e.g., AVL, Red-Black, Treap, Splay Tree).

Self-balancing BSTs optimize search, insertion, and deletion, making them ideal for applications like database indexing, memory management, and priority queues.

Self-balancing BST operations#

Self-balancing BSTs maintain balanced structures to ensure efficient operations.

Inserting a node

Perform a standard BST insertion.
Rebalance the tree using rotations if necessary.
Ensure height remains $O(\log n)$ for optimal performance.

Deleting a node

Locate the node to delete and remove it using BST rules.
If needed, replace it with the in-order successor or predecessor.
Rebalance the tree with rotations to maintain $O(\log n)$ height.

Searching for a node

Traverse the tree from the root, following BST order properties.
Return true if the key is found; otherwise, return false.
Runs in $O(\log n)$ time due to the balanced structure.

The overall space required for a BST is linear, $O(n)$ .

Self-balancing BST implementation in JavaScript#

We will go through the implementation step by step. First, we will create a definition for BSTNode and initialize the variables.

class SelfBalancingBST {
  constructor() {
    this.root = null;
  }
  // Get the height of a node (handles null nodes)
  getHeight(node) {
    return node ? node.height : 0;
  }
  // Get balance factor (left height - right height)
  getBalanceFactor(node) {
    return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
  }
  // Left rotation (for right-heavy trees)
  rotateLeft(node) {
    let newRoot = node.right;
    node.right = newRoot.left;
    newRoot.left = node;
    // Update heights
    node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
    newRoot.height = Math.max(this.getHeight(newRoot.left), this.getHeight(newRoot.right)) + 1;
    return newRoot;
  }
  // Right Rotation (for left-heavy trees)
  rotateRight(node) {
    let newRoot = node.left;
    node.left = newRoot.right;
    newRoot.right = node;
    // Update heights
    node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
    newRoot.height = Math.max(this.getHeight(newRoot.left), this.getHeight(newRoot.right)) + 1;
    return newRoot;
  }
  // Insert a value while maintaining balance
  insert(node, value) {
    if (!node) return new BSTNode(value);
    if (value < node.value) node.left = this.insert(node.left, value);
    else if (value > node.value) node.right = this.insert(node.right, value);
    else return node; // Ignore duplicates
    // Update height
    node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
    // Get balance factor
    let balance = this.getBalanceFactor(node);
    // Perform rotations if unbalanced
    if (balance > 1 && value < node.left.value) return this.rotateRight(node); // Left-Left case
    if (balance < -1 && value > node.right.value) return this.rotateLeft(node); // Right-Right case
    if (balance > 1 && value > node.left.value) {
      node.left = this.rotateLeft(node.left);
      return this.rotateRight(node); // Left-Right case
    }
    if (balance < -1 && value < node.right.value) {
      node.right = this.rotateRight(node.right);
      return this.rotateLeft(node); // Right-Left case
    }
    return node;
  }
  // Public method to add value
  add(value) {
    this.root = this.insert(this.root, value);
  }
  // Search for a value in the BST
  search(node, value) {
    if (!node) return false;
    if (value === node.value) return true;
    return value < node.value ? this.search(node.left, value) : this.search(node.right, value);
  }
  // Public method to check if a value exists
  contains(value) {
    return this.search(this.root, value);
  }
  // Find the node with the smallest value (for deletion)
  getMinValueNode(node) {
    while (node.left) node = node.left;
    return node;
  }
  // Delete a node and rebalance the tree
  delete(node, value) {
    if (!node) return node;
    if (value < node.value) node.left = this.delete(node.left, value);
    else if (value > node.value) node.right = this.delete(node.right, value);
    else {
      if (!node.left || !node.right) return node.left || node.right; // One or no child
      let temp = this.getMinValueNode(node.right);
      node.value = temp.value;
      node.right = this.delete(node.right, temp.value);
    }
    if (!node) return node; // If tree had only one node
    // Update height
    node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
    // Get balance factor
    let balance = this.getBalanceFactor(node);
    // Rebalance the tree if needed
    if (balance > 1 && this.getBalanceFactor(node.left) >= 0) return this.rotateRight(node);
    if (balance > 1 && this.getBalanceFactor(node.left) < 0) {
      node.left = this.rotateLeft(node.left);
      return this.rotateRight(node);
    }
    if (balance < -1 && this.getBalanceFactor(node.right) <= 0) return this.rotateLeft(node);
    if (balance < -1 && this.getBalanceFactor(node.right) > 0) {
      node.right = this.rotateRight(node.right);
      return this.rotateLeft(node);
    }
    return node;
  }
  // Public method to remove a value
  remove(value) {
    this.root = this.delete(this.root, value);
  }
}

Implementation of BST operations

// Example Usage
const bst = new SelfBalancingBST();
// Insert elements
bst.add(30);
bst.add(20);
bst.add(40);
bst.add(10);
bst.add(25);
bst.add(35);
bst.add(50);
console.log("Search Results:");
console.log("40:", bst.contains(40)); // true
console.log("25:", bst.contains(25)); // true
console.log("60:", bst.contains(60)); // false
// Delete a node and check again
bst.remove(20);
console.log("\nAfter Deletion:");
console.log("20:", bst.contains(20)); // false
console.log("25:", bst.contains(25)); // true
console.log("10:", bst.contains(10)); // true

Mastering Data Structures and Sorting Algorithms in JavaScript

Are you ready to become a top-notch JavaScript developer? Understand two of the most important concepts in programming - Data Structures & Sorting Algorithms. Learn to make efficient algorithms that save space and time if you want to excel in the field of software development. Take this interactive course to find out how to employ the most effective data structure in any scenario. This course covers sorting algorithms and their time complexity using JavaScript along with various data structures like Trees, Graphs, Heaps, Linked lists and many more.

3hrs

Beginner

34 Playgrounds

304 Illustrations

Let’s move forward to talk about segment trees.

Segment trees in JavaScript#

A segment tree is a tree-like data structure used for efficient range queries and updates on an array. It is widely used in applications like range sum queries, minimum/maximum queries, and frequency counting while supporting fast updates.

A segment tree is represented as an array-based binary tree where:

The root node represents the entire array.
A left child represents the first half of the segment.
A right child represents the second half of the segment.
Each parent node stores merged information from its two child nodes.

For an array of size n, a segment tree requires 4 * n memory to store nodes efficiently.

Key properties of segment trees#

Binary tree structure, where each node stores information about various elements.
Built-in $O(n)$ time, allowing efficient $O(\log n)$ queries and updates.
Supports operations like sum, minimum, maximum, GCD, and XOR over a range.
Each node stores aggregated data for a segment of the array.
Leaf nodes represent individual elements, while internal nodes store the merged results of their children.

Example of a segment tree#

Let’s take an example of Sum Query. A Sum Query in a segment tree is a technique used to quickly find the sum of elements within a given range in an array. Instead of iterating through the array (which takes $O(n)$ time), a segment tree precomputes and stores sums for different segments, allowing $O(\log n)$ query time.

Given array: [1, 3, 5, 7, 9, 11]

Corresponding Segment Tree:

Here, each internal node stores the sum of its child nodes.

Query (sum of index 1 to 4) → 3 + 5 + 7 + 9 = 24 ( $O(\log n)$ time).
Update (change index 2 to 6) → Updates only O(log n) nodes, making it highly efficient.

Let’s see if we can do operations with segment trees.

Segment tree operations#

Querying a range (Sum, Min, Max, GCD, etc.)

Traverse from root to relevant nodes using divide and conquer.
Return stored values for the queried range.
Runs in $O(\log n)$ time.

Updating a value

Locate the index in the tree and update it.
Recalculate parent nodes recursively.
Runs in $O(\log n)$ time.

Building the segment tree

Recursively split the array into segments.
Store merged results in parent nodes.
Runs in $O(n)$ time.

The space complexity of a segment tree is linear $O(n)$ .

Implementing segment trees in JavaScript#

A segment tree is a tree-like structure in which each node represents a segment of an array. It allows fast-range queries and updates.

class SegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(arr, 0, 0, this.n - 1);
  }
  // Build the segment tree
  build(arr, node, start, end) {
    if (start === end) {
      this.tree[node] = arr[start]; // Leaf node stores the actual array element
    } else {
      let mid = Math.floor((start + end) / 2);
      this.build(arr, 2 * node + 1, start, mid);
      this.build(arr, 2 * node + 2, mid + 1, end);
      this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2]; // Merge child nodes
    }
  }
  // Range Sum Query
  query(node, start, end, L, R) {
    if (start > R || end < L) return 0; // No overlap
    if (start >= L && end <= R) return this.tree[node]; // Complete overlap
    let mid = Math.floor((start + end) / 2);
    return (
      this.query(2 * node + 1, start, mid, L, R) +
      this.query(2 * node + 2, mid + 1, end, L, R)
    );
  }
  // Update a value in the segment tree
  update(node, start, end, idx, newValue) {
    if (start === end) {
      this.tree[node] = newValue; // Update leaf node
    } else {
      let mid = Math.floor((start + end) / 2);
      if (idx <= mid) {
        this.update(2 * node + 1, start, mid, idx, newValue);
      } else {
        this.update(2 * node + 2, mid + 1, end, idx, newValue);
      }
      this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2]; // Recalculate parent
    }
  }
  // Public method for querying
  rangeSum(L, R) {
    return this.query(0, 0, this.n - 1, L, R);
  }
  // Public method for updating
  modify(idx, newValue) {
    this.update(0, 0, this.n - 1, idx, newValue);
  }
}
// Example Usage
const arr = [1, 3, 5, 7, 9, 11];
const segmentTree = new SegmentTree(arr);
console.log("Range Sum (1-4):", segmentTree.rangeSum(1, 4)); // Output: 24
// Update index 2 to value 6
segmentTree.modify(2, 6);
console.log("Range Sum (1-4) after update:", segmentTree.rangeSum(1, 4)); // Output: 25

The code first constructs a segment tree for the array [1, 3, 5, 7, 9, 11], enabling fast-range sum queries and updates.

The initial query rangeSum(1,4) calculates the sum of elements from index 1 to 4 (3 + 5 + 7 + 9 = 24).
After updating index 2 from 5 to 6, the tree efficiently updates only the affected nodes instead of rebuilding the entire structure.
A second query for the same range now returns 25, reflecting the updated value (3 + 6 + 7 + 9 = 25).

While segment trees provide flexible range queries and updates, binary indexed trees (BIT) offer a more compact and efficient alternative for prefix sum calculations and dynamic updates with simpler implementation and lower memory usage.

Binary indexed trees (BIT) in JavaScript#

A binary indexed tree (BIT), or a Fenwick tree, is a tree-like data structure that efficiently processes prefix sum and update queries on an array. It is particularly useful for scenarios requiring frequent updates and prefix sum calculations, such as statistical computations, range sum queries, and competitive programming.

Key properties of binary indexed trees#

Uses an array-based structure instead of explicit tree nodes.
Supports efficient prefix sum queries in $O(\log n)$ time.
Updates elements dynamically without modifying the entire array.
Each index stores aggregated values for a certain range of elements.
Uses bitwise operations to determine parent-child relationships.

BIT representation and structure#

A binary indexed tree stores values in an array, where:

Each index represents a cumulative sum of certain elements.
Parent-child relationships are determined by binary representation.
The last set bit (LSB) helps identify each index’s range.

For an array of size n, a BIT requires only $O(n)$ space and supports $O(log n)$ updates and queries.

Example of a binary indexed tree #

A binary indexed tree efficiently computes prefix sums by storing cumulative values at different indexes, reducing query time from $O(n)$ to $O(\log n)$ . Each index in the BIT represents a sum over a specific range, determined by its least significant bit (LSB).

Given array: [1, 3, 5, 7, 9, 11]

Corresponding BIT representation:

Binary indexed tree operations#

Querying a prefix sum

Traverse parent nodes using bitwise operations to accumulate the sum.
Runs in $O(\log n)$ time, making it significantly faster than a normal array sum.

Updating an element

Locate the affected index and update its parent nodes.
Only updates $O(\log n)$ elements, ensuring high efficiency.

Building the BIT

Uses the update function iteratively to construct the tree in $O(n \log n)$ time.

BITs maintain a space complexity of $O(n)$ .

Implementing binary indexed tree in JavaScript#

A binary indexed tree allows fast-range queries and updates while maintaining a compact structure.

class BinaryIndexedTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(this.n + 1).fill(0);
    this.build(arr);
  }
  // Build the BIT from an array
  build(arr) {
    for (let i = 0; i < this.n; i++) {
      this.update(i, arr[i]);
    }
  }
  // Update a value at index idx by adding delta
  update(idx, delta) {
    idx++; // BIT uses 1-based indexing
    while (idx <= this.n) {
      this.tree[idx] += delta;
      idx += idx & -idx; // Move to parent node
    }
  }
  // Get prefix sum from index 0 to idx
  prefixSum(idx) {
    let sum = 0;
    idx++; // BIT uses 1-based indexing
    while (idx > 0) {
      sum += this.tree[idx];
      idx -= idx & -idx; // Move to previous node
    }
    return sum;
  }
  // Get sum of elements in range [L, R]
  rangeSum(L, R) {
    return this.prefixSum(R) - this.prefixSum(L - 1);
  }
}
// Example Usage
const arr = [1, 3, 5, 7, 9, 11];
const bit = new BinaryIndexedTree(arr);
console.log("Prefix Sum (0-4):", bit.prefixSum(4)); // Output: 25
// Update index 2 by adding 1 (changing 5 to 6)
bit.update(2, 1);
console.log("Prefix Sum (0-4) after update:", bit.prefixSum(4)); // Output: 26

Key properties of graphs#

Nodes (Vertices): The fundamental units representing elements in the graph.
Edges: Connections between nodes can be directed (one-way) or undirected (two-way).
Adjacency representation: Graphs can be stored using an adjacency list (efficient for sparse graphs) or an adjacency matrix (useful for dense graphs).
Connected components: A connected graph has a path between every pair of nodes.
Cyclic and acyclic structures: Graphs can contain cycles (e.g., in road networks) or be acyclic (e.g., dependency graphs).

Graph operations#

Adding vertices and edges

Vertices are stored in an adjacency list, and edges are added to connect them.
Undirected graphs store connections in both directions, while directed graphs maintain one-way edges.

Graph traversal (Search)

Breadth-first search (BFS) explores nodes level by level, making it useful for shortest-path algorithms.
Depth-first search (DFS) explores as deep as possible before backtracking, making it ideal for cycle detection and connectivity checks.

Graph algorithms#

Dijkstra’s algorithm: Finds the shortest path from a single source in weighted graphs.
Kruskal’s and Prim’s algorithms: Compute the minimum spanning tree (MST).
Topological sorting: Orders nodes in a directed acyclic graph (DAG) based on dependencies.

Graph representation in JavaScript#

A graph can be represented using an adjacency list, where each node stores a list of its neighboring nodes.

class Graph {
  constructor() {
    this.adjList = new Map(); // Stores graph as an adjacency list
  }
  // Add a vertex to the graph
  addVertex(vertex) {
    if (!this.adjList.has(vertex)) {
      this.adjList.set(vertex, []);
    }
  }
  // Add an edge (connection) between two vertices
  addEdge(vertex1, vertex2, directed = false) {
    this.adjList.get(vertex1).push(vertex2);
    if (!directed) {
      this.adjList.get(vertex2).push(vertex1); // For undirected graphs
    }
  }
  // Print the graph structure
  printGraph() {
    for (let [vertex, edges] of this.adjList) {
      console.log(vertex, "->", edges.join(", "));
    }
  }
}
// Example Usage
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "C");
graph.printGraph();

Key advantages of Graphs#

Graphs are essential for representing complex relationships between entities, making them a fundamental data structure in various real-world applications.

Used in social networks, road maps, and web crawling.
Supports BFS, DFS, and shortest path computations.
It can be stored using adjacency lists (efficient) or adjacency matrices (dense graphs).
Used in AI, game development, recommendation systems, and scheduling tasks.

Using an adjacency list, graphs support operations like traversals in $O(n + m)$ time (with $n$ vertices and $m$ edges), while basic insertion can be $O(1)$ . Their space complexity is $O(n + m)$ .

We’ve covered multiple advanced data structures in JavaScript. If you’re gearing up for technical interviews, explore Educative’s courses for structured learning and hands-on practice! 🚀

Level up your data structures game for interviews!

Data Structures for Coding Interviews in JavaScript

Data structures are amongst the very fundamentals of Computer Science and are often a core decision in developing efficient programs. Consequently, they are also largely categorized as a vital benchmark of computer science knowledge when it comes to industry interviews. This course contains a detailed review of all the common data structures and provides implementation level details in JavaScript to allow readers to become well equipped with all the different data structures they can leverage to write better code!

35hrs

Beginner

65 Challenges

24 Quizzes

Feature	Trie	Self-Balancing BST	Segment Tree	Binary Indexed Tree (BIT)	Graph
Data structure type	Tree-like structure	Binary Search Tree with auto-balancing	Tree-like structure	Array-based tree structure	Node-based structure with edges
Primary use case	Efficient string storage and retrieval	Fast-ordered data operations	Efficient range of queries and updates	Efficient prefix sum and updates	Represents relationships between elements
Insertion complexity	O(n) (n = length of word)	O(log n)	O(n) (for build)	O(log n)	O(1) (Adjacency list), O(n²) (Adjacency matrix)
Search complexity	O(n)	O(log n)	O(log n)	O(log n)	O(1) (Adjacency list), O(n²) (Adjacency matrix)
Update complexity	O(n)	O(log n)	O(log n)	O(log n)	O(1) (Adjacency list), O(n²) (Adjacency matrix)
Space complexity	O(m × n), where m is the word length, and n is the number of words	O(n)	O(n)	O(n)	O(n+m) where n vertices and m edges
Memory usage	High (depends on word size)	Moderate (depends on balance factor)	High (4n memory for n elements)	Low (O(n) space)	Varies (Adjacency list: low, Adjacency matrix: high)
Implementation in JavaScript	Uses nodes with character mapping and child pointers	Uses nodes with left/right pointers and a balance property	Uses an array-based tree with recursive splitting	Uses an array with bitwise manipulation for updates	Uses adjacency list (Map/Set) or adjacency matrix (2D array)
Traversal method	DFS/Recursive traversal	Inorder, Preorder, Postorder	Divide and Conquer traversal	Bitwise traversal	BFS, DFS, Dijkstra, Floyd-Warshall
Ideal for	Autocomplete, spell-check, dictionary lookups	Database indexing, priority queues, and dynamic sets	Range sum, min/max, frequency count, RMQ	Dynamic prefix sums, cumulative frequency tables	Networking, social graphs, shortest paths, web crawling

Wrapping up and next steps#

Mastering these advanced data structures isn’t just about passing coding interviews—it’s about building efficient, scalable systems in the real world. Whether you’re optimizing a search feature, building a recommendation engine, or handling large datasets, these tools will be your secret weapon. Understanding their strengths and trade-offs will enhance your problem-solving skills and boost your algorithm design and technical interview efficiency.

Happy learning!

Continue reading about JavaScript#

Frequently Asked Questions

What are data structures in JavaScript?

Data structures in JavaScript are ways to organize and store data efficiently. They include arrays, objects, stacks, queues, trees, graphs, and hash tables, each serving different purposes in problem-solving and algorithm design.

Is DSA good or bad in JavaScript?

DSA (Data structures and algorithms) is highly useful in JavaScript, especially for backend systems, real-time applications, and competitive programming. Lower-level languages like C++ or Java may offer better memory management.

How can we choose the right data structure?

Choosing the right data structure depends on the problem’s requirements—arrays for simple collections, hash tables for fast lookups, trees for hierarchical data, graphs for network relationships, and queues/stacks for ordered processing.

What is a graph in JavaScript?

A graph in JavaScript is a nonlinear data structure consisting of nodes (vertices) and edges (connections) used to represent relationships. It is commonly implemented with adjacency lists (Map/Set) or adjacency matrices (2D arrays).

Written By:

Jerry Ejonavi

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

YouTubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

Data structures 101: Advanced data structures in JavaScript

JavaScript advanced data structures#

Trie data structure#

Trie data structure key properties#

Trie size based on alphabet count#

Implementing tries in JavaScript#

Structure of a trie node#

How do trie nodes work?#

Creating a trie in JavaScript#

Trie operations: Insertion, search, and deletion#

Self-balancing BST in JavaScript#

Common types of self-balancing BSTs#

Structure of self-balancing BSTs#

Key properties of self-balancing BSTs#

Example of a self-balancing BST#

Self-balancing BST operations#

Self-balancing BST implementation in JavaScript#

Segment trees in JavaScript#

Key properties of segment trees#

Example of a segment tree#

Segment tree operations#

Implementing segment trees in JavaScript#

Binary indexed trees (BIT) in JavaScript#

Key properties of binary indexed trees#

BIT representation and structure#

Example of a binary indexed tree #

Binary indexed tree operations#

Implementing binary indexed tree in JavaScript#

Graph data structures#

Key properties of graphs#

Graph operations#

Graph algorithms#

Graph representation in JavaScript#

Key advantages of Graphs#

Data structures in JavaScript: A Comparison#

Wrapping up and next steps#

Continue reading about JavaScript#

Frequently Asked Questions

What are data structures in JavaScript?

Is DSA good or bad in JavaScript?

How can we choose the right data structure?

What is a graph in JavaScript?