Data Structure Representations: Why They’re Built the Way They Are

Introduction

This is the most important file in your interview preparation.

The confusion isn’t about what trees or graphs are. You know that. The confusion is: Why do we represent them differently depending on the context?

A tree can be represented as: 1. An array (compact, cache-friendly, for heaps) 2. Objects with pointers (flexible, for most problems)

A graph can be represented as: 1. An adjacency matrix (fast edge lookup) 2. An adjacency list (space-efficient) 3. An edge list (simple)

Why the choices? Memory layout. Trade-offs between speed and space. What operations you need to optimize.

Computers have flat memory: arrays of bytes. Everything you build is either:

Contiguous: An array. Fast to iterate, good cache locality, but fixed size or requires reallocation.
Scattered with pointers: Linked structures. Flexible, but more memory overhead and poor cache performance.

This document explains the why behind each representation.

Part 1: The Fundamental Question — Memory Layout

Contiguous Memory (Arrays)

When you create an array in JavaScript, V8 allocates a contiguous block of memory.

const arr = [10, 20, 30, 40];
// In memory (simplified):
// Address:  0x1000  0x1008  0x1010  0x1018
// Value:    10      20      30      40

Advantages: - O(1) access by index: arr[2] just computes address + 2 * 8 bytes - Cache-friendly: reading one element loads nearby elements into CPU cache - Compact: no overhead

Disadvantages: - Fixed size (in low-level languages) or reallocation required (JavaScript Arrays) - Can’t efficiently insert in the middle - Wastes space if you don’t use all slots

Scattered Memory (Pointers)

When you create an object with references, memory is scattered.

const node = { val: 10, next: null };
node.next = { val: 20, next: null };
// In memory (simplified):
// node:           address 0x2000
//   val: 10       at 0x2000
//   next: pointer to 0x3000
//
// node.next:      address 0x3000
//   val: 20       at 0x3000
//   next: null

Advantages: - Flexible: easily add/remove nodes - No reallocation needed - Can create any shape

Disadvantages: - Pointer overhead (extra memory per node) - Poor cache performance (next node is far away in memory) - O(1) access by position requires traversal

The Trade-off

Use contiguous memory when: - You need fast random access - You want cache efficiency - The structure is complete (like a heap)

Use scattered memory when: - Structure is irregular (some nodes have many children, others few) - You need to frequently add/remove nodes - Simplicity matters more than speed (most interview problems)

Part 2: Representing Common Data Structures

Trees

Representation 1: Array (Compact)

For a complete binary tree (all levels filled except possibly the last), use an array.

Index formula: - Left child of node at index i: 2i + 1 - Right child of node at index i: 2i + 2 - Parent of node at index i: floor((i - 1) / 2)

// Tree:        0
//             / \
//            1   2
//           / \ / \
//          3  4 5  6

// Array representation:
const arr = [0, 1, 2, 3, 4, 5, 6];
//  Index:  0  1  2  3  4  5  6

// Access left child of node at index 1:
const leftChildIndex = 2 * 1 + 1; // = 3
const leftChild = arr[3]; // = 3

// Access parent of node at index 5:
const parentIndex = Math.floor((5 - 1) / 2); // = 2
const parent = arr[2]; // = 2

Memory layout (contiguous):

// Addresses:   0x1000  0x1008  0x1010  0x1018  0x1020  0x1028  0x1030
// Values:      0       1       2       3       4       5       6
// All adjacent in memory — very cache-friendly

When to use: - Heaps (binary heaps for priority queues) - Complete binary trees - When you need compact storage

When NOT to use: - Sparse trees (wastes space with null values) - Trees where you frequently add/remove nodes at arbitrary positions

Visual representation:

Representation 2: Objects with References (Flexible)

For most interview problems, represent a tree as nodes with references.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// Build the tree:     1
//                    / \
//                   2   3
const tree = new TreeNode(1,
  new TreeNode(2),
  new TreeNode(3)
);

Memory layout (scattered):

// TreeNode at address 0x2000:
//   val: 1
//   left: pointer to 0x3000
//   right: pointer to 0x4000
//
// TreeNode at address 0x3000:
//   val: 2
//   left: null
//   right: null
//
// TreeNode at address 0x4000:
//   val: 3
//   left: null
//   right: null

When to use: - Most interview problems (DFS, BFS, path problems) - Arbitrary tree shapes - Easy to understand and debug

When NOT to use: - If you need compact storage (but this rarely matters in interviews)

Converting Between Representations

From level-order array to node-based tree:

// Input: [3, 9, 20, null, null, 15, 7]
// This is level-order traversal
// Tree:      3
//           / \
//          9  20
//           / \
//          15  7

function arrayToTree(arr) {
  if (!arr || arr.length === 0 || arr[0] === null) return null;

  const root = new TreeNode(arr[0]);
  const queue = [root];
  let i = 1;

  while (queue.length > 0 && i < arr.length) {
    const node = queue.shift();

    // Add left child
    if (i < arr.length && arr[i] !== null) {
      node.left = new TreeNode(arr[i]);
      queue.push(node.left);
    }
    i++;

    // Add right child
    if (i < arr.length && arr[i] !== null) {
      node.right = new TreeNode(arr[i]);
      queue.push(node.right);
    }
    i++;
  }

  return root;
}

Graphs

Graphs have multiple representations, each with different trade-offs.

Representation 1: Adjacency Matrix

A 2D array where matrix[i][j] represents an edge from node i to node j.

For unweighted graphs:

// Graph with 4 nodes and edges: 0->1, 1->2, 2->3, 3->0
const adjacencyMatrix = [
  [0, 1, 0, 0],  // Node 0: connects to 1
  [0, 0, 1, 0],  // Node 1: connects to 2
  [0, 0, 0, 1],  // Node 2: connects to 3
  [1, 0, 0, 0]   // Node 3: connects to 0
];
// matrix[0][1] = 1 means edge from 0 to 1
// matrix[0][2] = 0 means no edge from 0 to 2

For weighted graphs:

// Same graph but with weights (distances)
const adjacencyMatrix = [
  [0, 5, 0, 0],    // Node 0: edge to 1 with weight 5
  [0, 0, 3, 0],    // Node 1: edge to 2 with weight 3
  [0, 0, 0, 2],    // Node 2: edge to 3 with weight 2
  [1, 0, 0, 0]     // Node 3: edge to 0 with weight 1
];
// matrix[i][j] = weight of edge from i to j (or 0/Infinity if no edge)

Time complexity: - Edge lookup: O(1) — check matrix[i][j] - Iterate all edges: O(V²) — must check every cell - Space: O(V²) — always, even for sparse graphs

When to use: - Dense graphs (many edges) - Need fast edge lookup: "Is there an edge between X and Y?" - Problems asking about all pairs: all-pairs shortest path - Small graphs (V ≤ 1000)

When NOT to use: - Sparse graphs (wastes space) - Need to iterate neighbors frequently (slower than adjacency list)

Visual representation:

Representation 2: Adjacency List

A map (or object) where each key is a node and the value is a list of its neighbors.

// Same graph: 0->1, 1->2, 2->3, 3->0
const adjacencyList = {
  0: [1],           // Node 0: connects to node 1
  1: [2],           // Node 1: connects to node 2
  2: [3],           // Node 2: connects to node 3
  3: [0]            // Node 3: connects to node 0
};
// Access neighbors of node 1: adjacencyList[1] = [2]

For weighted graphs:

// With weights, store [neighbor, weight] pairs
const adjacencyList = {
  0: [[1, 5]],              // Node 0: edge to 1 with weight 5
  1: [[2, 3]],              // Node 1: edge to 2 with weight 3
  2: [[3, 2]],              // Node 2: edge to 3 with weight 2
  3: [[0, 1]]               // Node 3: edge to 0 with weight 1
};

Using a Map (preferred for JavaScript):

const adjacencyList = new Map();
adjacencyList.set(0, [1]);
adjacencyList.set(1, [2]);
adjacencyList.set(2, [3]);
adjacencyList.set(3, [0]);

Time complexity: - Edge lookup: O(degree of node) — must search the neighbor list - Iterate all edges: O(V + E) — visit each node once, and each edge once - Space: O(V + E) — proportional to actual structure

When to use: - Sparse graphs (most interview problems) - Need to iterate neighbors: BFS, DFS - Want space-efficient representation - Standard choice for most problems

When NOT to use: - Need O(1) edge lookup between arbitrary pairs

Visual representation:

Representation 3: Edge List

An array of [from, to] pairs (or [from, to, weight] for weighted graphs).

// Same graph as edges
const edges = [
  [0, 1],  // Edge from 0 to 1
  [1, 2],  // Edge from 1 to 2
  [2, 3],  // Edge from 2 to 3
  [3, 0]   // Edge from 3 to 0
];

// For weighted:
const weightedEdges = [
  [0, 1, 5],  // Edge from 0 to 1 with weight 5
  [1, 2, 3],  // Edge from 1 to 2 with weight 3
  [2, 3, 2],  // Edge from 2 to 3 with weight 2
  [3, 0, 1]   // Edge from 3 to 0 with weight 1
];

Time complexity: - Edge lookup: O(E) — must search all edges - Iterate all edges: O(E) — just iterate the array - Space: O(E)

When to use: - Input format in many problems - Algorithms that process all edges (Kruskal’s MST, Bellman-Ford) - Simple, easy to understand

When NOT to use: - Need to lookup edges or neighbors efficiently

Representation 4: Implicit Graph (Grids/Matrices)

For grid-based problems, don’t build an explicit graph. The grid itself is the graph.

// Grid:
// . # .
// . . .
// . # .
// Where . is passable, # is wall

const grid = [
  [0, 1, 0],
  [0, 0, 0],
  [0, 1, 0]
];

// Each cell (i, j) is a node
// Neighbors are: (i-1,j), (i+1,j), (i,j-1), (i,j+1)

function getNeighbors(i, j) {
  const neighbors = [];
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // up, down, left, right

  for (const [di, dj] of directions) {
    const ni = i + di, nj = j + dj;
    if (ni >= 0 && ni < grid.length && nj >= 0 && nj < grid[0].length) {
      if (grid[ni][nj] === 0) { // passable
        neighbors.push([ni, nj]);
      }
    }
  }
  return neighbors;
}

// BFS on implicit graph
function bfs(grid, start, end) {
  const queue = [start];
  const visited = new Set([start.toString()]);

  while (queue.length > 0) {
    const [i, j] = queue.shift();
    if (i === end[0] && j === end[1]) return true;

    for (const [ni, nj] of getNeighbors(i, j)) {
      const key = `${ni},${nj}`;
      if (!visited.has(key)) {
        visited.add(key);
        queue.push([ni, nj]);
      }
    }
  }
  return false;
}

When to use: - Grid-based problems (island counting, maze solving, shortest path in grid) - Saves memory (no explicit graph structure) - Natural representation for the problem

Visual representation:

Building Data Structures from Input

In interviews, you receive input in a specific format. You need to convert it.

Building an Adjacency List from an Edge List

function edgeListToAdjacencyList(n, edges) {
  // n = number of nodes (0 to n-1)
  // edges = [[from, to], ...]
  const adj = {};
  for (let i = 0; i < n; i++) {
    adj[i] = [];
  }
  for (const [from, to] of edges) {
    adj[from].push(to);
  }
  return adj;
}

// Example:
const n = 4;
const edges = [[0, 1], [1, 2], [2, 3], [3, 0]];
const adj = edgeListToAdjacencyList(n, edges);
// Result:
// { 0: [1], 1: [2], 2: [3], 3: [0] }

Building an Adjacency Matrix from an Edge List

function edgeListToAdjacencyMatrix(n, edges) {
  // Create n × n matrix
  const matrix = Array(n).fill(0).map(() => Array(n).fill(0));
  for (const [from, to] of edges) {
    matrix[from][to] = 1;
  }
  return matrix;
}

// Example:
const n = 4;
const edges = [[0, 1], [1, 2], [2, 3], [3, 0]];
const matrix = edgeListToAdjacencyMatrix(n, edges);
// Result:
// [[0, 1, 0, 0],
//  [0, 0, 1, 0],
//  [0, 0, 0, 1],
//  [1, 0, 0, 0]]

Building an Adjacency List from an Adjacency Matrix

function matrixToAdjacencyList(matrix) {
  const adj = {};
  for (let i = 0; i < matrix.length; i++) {
    adj[i] = [];
    for (let j = 0; j < matrix[i].length; j++) {
      if (matrix[i][j] === 1) {
        adj[i].push(j);
      }
    }
  }
  return adj;
}

// Example:
const matrix = [
  [0, 1, 0, 0],
  [0, 0, 1, 0],
  [0, 0, 0, 1],
  [1, 0, 0, 0]
];
const adj = matrixToAdjacencyList(matrix);
// Result:
// { 0: [1], 1: [2], 2: [3], 3: [0] }

Building a TreeNode from Level-Order Array

function arrayToTree(arr) {
  if (!arr || arr.length === 0 || arr[0] === null) return null;

  const root = new TreeNode(arr[0]);
  const queue = [root];
  let i = 1;

  while (queue.length > 0 && i < arr.length) {
    const node = queue.shift();

    // Left child
    if (i < arr.length && arr[i] !== null) {
      node.left = new TreeNode(arr[i]);
      queue.push(node.left);
    }
    i++;

    // Right child
    if (i < arr.length && arr[i] !== null) {
      node.right = new TreeNode(arr[i]);
      queue.push(node.right);
    }
    i++;
  }

  return root;
}

// Example:
const arr = [3, 9, 20, null, null, 15, 7];
const tree = arrayToTree(arr);
// Builds:
//      3
//     / \
//    9  20
//      / \
//     15  7

Part 3: How Interview Input Arrives

Interview problems give you data in specific formats. You need to recognize and work with them.

Trees as Level-Order Arrays

Input format: [3, 9, 20, null, null, 15, 7]

This represents a level-order (breadth-first) traversal where null indicates missing children.

What to do: 1. If the problem is easy (just traversing), work with the array directly 2. If you need to modify the tree or it’s easier to use recursion, build a TreeNode structure

// Option 1: Work with array directly
function sumTree(arr) {
  let sum = 0;
  for (const val of arr) {
    if (val !== null) sum += val;
  }
  return sum;
}

// Option 2: Build TreeNode and use recursion
function sumTreeRecursive(node) {
  if (!node) return 0;
  return node.val + sumTreeRecursive(node.left) + sumTreeRecursive(node.right);
}

const arr = [3, 9, 20, null, null, 15, 7];
const tree = arrayToTree(arr);
console.log(sumTreeRecursive(tree)); // 74

Graphs as Edge Lists

Input format: edges = [[0,1], [1,2], [2,3], [3,0]], n = 4

This gives you edges and the number of nodes.

What to do: 1. If the problem asks about neighbors, convert to adjacency list 2. If the problem asks about arbitrary edge lookup, convert to adjacency matrix 3. If the problem is about MST or processes all edges, keep as edge list

// Most common: convert to adjacency list for BFS/DFS
const edges = [[0, 1], [1, 2], [2, 3], [3, 0]];
const n = 4;
const adj = edgeListToAdjacencyList(n, edges);

// Now you can easily do BFS
function bfs(start) {
  const visited = new Set();
  const queue = [start];
  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node);

    for (const neighbor of adj[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

Grids as 2D Arrays

Input format: grid = [[1,1,1],[1,0,1],[1,1,1]]

This is already in matrix form. Each cell is a node.

What to do: - Treat as implicit graph - Compute neighbors on the fly - Use BFS for shortest path or DFS for reachability

const grid = [[1, 1, 1], [1, 0, 1], [1, 1, 1]];

function getNeighbors(i, j) {
  const neighbors = [];
  for (const [di, dj] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
    const ni = i + di, nj = j + dj;
    if (ni >= 0 && ni < grid.length && nj >= 0 && nj < grid[0].length) {
      neighbors.push([ni, nj]);
    }
  }
  return neighbors;
}

// BFS for shortest path
function shortestPath(grid, start, end) {
  const queue = [start];
  const visited = new Set([start.toString()]);
  const distance = { [start.toString()]: 0 };

  while (queue.length > 0) {
    const [i, j] = queue.shift();
    const key = `${i},${j}`;

    if (i === end[0] && j === end[1]) {
      return distance[key];
    }

    for (const [ni, nj] of getNeighbors(i, j)) {
      const nextKey = `${ni},${nj}`;
      if (!visited.has(nextKey)) {
        visited.add(nextKey);
        distance[nextKey] = distance[key] + 1;
        queue.push([ni, nj]);
      }
    }
  }

  return -1; // No path found
}

Part 4: When to Use Each Representation

Structure	Representation	Use When	Time: Neighbors
Time: Edge Lookup	Tree	Array	Complete binary tree, heap
O(1) compute	O(1)	Tree	TreeNode
General case, DFS	O(1) access	O(1)	Graph
Adjacency List	Most problems, sparse	O(degree)	O(degree)
Graph	Adjacency Matrix	Dense graph, frequent lookup	O(V)
O(1)	Graph	Edge List	Input format, Kruskal’s
O(E)	O(E)	Grid	Implicit (2D array)

Structure

Representation

Use When

Time: Neighbors

Time: Edge Lookup

Tree

Array

Complete binary tree, heap

O(1) compute

O(1)

Tree

TreeNode

General case, DFS

O(1) access

O(1)

Graph

Adjacency List

Most problems, sparse

O(degree)

Graph

Adjacency Matrix

Dense graph, frequent lookup

O(V)

O(1)

Graph

Edge List

Input format, Kruskal’s

O(E)

Grid

Implicit (2D array)

Summary: The Key Insight

The fundamental choice: Contiguous memory (array) vs scattered memory (pointers).

In interviews: 1. Understand the input format 2. Choose the representation that makes your algorithm simplest 3. Convert between representations as needed 4. For most problems: TreeNode for trees, adjacency list for graphs

You’ll see all of these representations across different problems. The key is understanding why each exists and when to use it.