Linked Lists and Binary Trees
Module 10 · Linked Lists and Binary Trees

Linked Lists and Binary Trees

Build linked lists and binary search trees from scratch using nodes and pointers — understanding traversal, insertion, and the tradeoffs compared to arrays.

Pointer-Based Data Structures

Arrays store elements in contiguous memory — each element is right next to the next. That gives O(1) random access (arr[5]) but makes inserting at the front O(n) because everything must shift.

Pointer-based structures connect nodes through references. Inserting at the front of a linked list is O(1) — just update a pointer. But random access requires traversal from the head: O(n).

Neither is strictly better. The right choice depends on your access patterns.


Singly Linked Lists

A singly linked list is a sequence of nodes where each node stores a value and a reference to the next node.

head → [1 | next] → [2 | next] → [3 | null]
class ListNode<T> {
  constructor(
    public value: T,
    public next: ListNode<T> | null = null,
  ) {}
}

class LinkedList<T> {
  private head: ListNode<T> | null = null;
  private length: number = 0;

  prepend(value: T): void {
    this.head = new ListNode(value, this.head);
    this.length++;
  }

  append(value: T): void {
    const node = new ListNode(value);
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) current = current.next;
      current.next = node;
    }
    this.length++;
  }

  delete(value: T): boolean {
    if (!this.head) return false;

    if (this.head.value === value) {
      this.head = this.head.next;
      this.length--;
      return true;
    }

    let current = this.head;
    while (current.next) {
      if (current.next.value === value) {
        current.next = current.next.next;
        this.length--;
        return true;
      }
      current = current.next;
    }
    return false;
  }

  toArray(): T[] {
    const result: T[] = [];
    let current = this.head;
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    return result;
  }

  get size(): number {
    return this.length;
  }
}

const list = new LinkedList<number>();
list.append(1);
list.append(2);
list.append(3);
list.prepend(0);
list.toArray()  // [0, 1, 2, 3]
list.delete(2);
list.toArray()  // [0, 1, 3]

Linked List vs. Array

OperationArrayLinked List
Access by indexO(1)O(n)
Insert at frontO(n) — shift allO(1)
Insert at endO(1) amortizedO(n) without tail pointer
Delete by valueO(n)O(n) search + O(1) remove
MemoryContiguous blockScattered, extra pointer per node
💻 Code Lab: Reversing a Linked List

Reversing a linked list in place is a classic interview problem. The key is to keep track of three pointers as you walk the list:

function reverseList<T>(head: ListNode<T> | null): ListNode<T> | null {
  let prev: ListNode<T> | null = null;
  let current = head;

  while (current) {
    const next = current.next;  // save the next node
    current.next = prev;        // reverse the pointer
    prev = current;             // advance prev
    current = next;             // advance current
  }

  return prev;  // prev is now the new head
}

// Before: 1 → 2 → 3 → null
// After:  3 → 2 → 1 → null

Walk through this step by step with a small list on paper to understand how the three-pointer technique works. This pattern appears in many linked list problems.


Doubly Linked Lists

A doubly linked list adds a prev pointer to each node, allowing traversal in both directions:

class DoublyListNode<T> {
  constructor(
    public value: T,
    public next: DoublyListNode<T> | null = null,
    public prev: DoublyListNode<T> | null = null,
  ) {}
}

The extra pointer makes removing a node by reference O(1) instead of O(n) (no need to find the previous node). This makes doubly linked lists the basis for the LRU cache — a common interview problem and real-world pattern.


Binary Trees

A binary tree is a hierarchical structure where each node has at most two children: left and right.

         4
        / \
       2   6
      / \ / \
     1  3 5  7
class TreeNode<T> {
  constructor(
    public value: T,
    public left: TreeNode<T> | null = null,
    public right: TreeNode<T> | null = null,
  ) {}
}

Tree Traversal

Three common ways to visit all nodes:

// In-order: left → root → right (produces sorted output for BSTs)
function inOrder<T>(node: TreeNode<T> | null, result: T[] = []): T[] {
  if (!node) return result;
  inOrder(node.left, result);
  result.push(node.value);
  inOrder(node.right, result);
  return result;
}

// Pre-order: root → left → right (useful for copying a tree)
function preOrder<T>(node: TreeNode<T> | null, result: T[] = []): T[] {
  if (!node) return result;
  result.push(node.value);
  preOrder(node.left, result);
  preOrder(node.right, result);
  return result;
}

// Post-order: left → right → root (useful for deleting a tree)
function postOrder<T>(node: TreeNode<T> | null, result: T[] = []): T[] {
  if (!node) return result;
  postOrder(node.left, result);
  postOrder(node.right, result);
  result.push(node.value);
  return result;
}

Binary Search Tree

A binary search tree (BST) enforces an ordering invariant:

  • Every node in the left subtree has a value less than the current node
  • Every node in the right subtree has a value greater than the current node

This invariant makes search, insertion, and deletion O(log n) on a balanced tree.

class BinarySearchTree {
  root: TreeNode<number> | null = null;

  insert(value: number): void {
    const node = new TreeNode(value);
    if (!this.root) {
      this.root = node;
      return;
    }

    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) { current.left = node; return; }
        current = current.left;
      } else {
        if (!current.right) { current.right = node; return; }
        current = current.right;
      }
    }
  }

  contains(value: number): boolean {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      current = value < current.value ? current.left : current.right;
    }
    return false;
  }

  toSortedArray(): number[] {
    return inOrder(this.root);
  }
}

const bst = new BinarySearchTree();
[5, 3, 7, 1, 4, 6, 8].forEach(n => bst.insert(n));
bst.contains(4)           // true
bst.contains(9)           // false
bst.toSortedArray()       // [1, 3, 4, 5, 6, 7, 8] — sorted!
⚠️ Common Pitfall: Unbalanced BSTs Degrade to O(n)

If you insert values in sorted order into a BST, every node goes to the right — the tree becomes a linked list and all operations degrade to O(n):

Insert: 1, 2, 3, 4, 5

1
 \
  2
   \
    3
     \
      4
       \
        5

Searching for 5 requires 5 comparisons — linear. Production trees use self-balancing algorithms (AVL trees, Red-Black trees) that automatically restructure on insert to maintain O(log n) height. JavaScript’s built-in Map and Set use hash tables rather than trees, but many databases and sorted containers are backed by balanced BSTs internally.


Breadth-First Search (BFS)

Breadth-first search visits all nodes level by level, using a queue:

function bfs(root: TreeNode<number> | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  const queue: TreeNode<number>[] = [root];

  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return result;
}

// For the BST above: [5, 3, 7, 1, 4, 6, 8] — level by level

BFS is the right approach when you need the shortest path or want to process nodes in level order.


🧠 Knowledge Check

What is the time complexity of search, insertion, and deletion in a balanced binary search tree?

Reveal Answer & Explanation

All three operations are O(log n) on a balanced BST.

At each node, you compare the target value to the current node and go left or right — eliminating half the remaining tree with each step. On a tree with n nodes, the height is log₂(n), so you make at most log₂(n) comparisons before reaching a leaf or finding the target.

This is the same reasoning as binary search on a sorted array — a BST makes it dynamic: you can insert and delete while maintaining the sorted structure, whereas inserting into a sorted array requires shifting elements (O(n)).

The key qualifier is balanced — an unbalanced tree can degrade to O(n). Self-balancing trees (AVL, Red-Black) maintain the balance invariant automatically.


Course Complete

You’ve now covered the full arc of this course — from the foundational values and types of JavaScript, through functions and programming paradigms, to the computer science foundations of algorithms and data structures.

The next step is applying everything you’ve learned: work through the FreeCodeCamp JavaScript Algorithms and Data Structures Certification, complete your team project (converting a JavaScript project to strictly typed TypeScript), and build the habit of analyzing your code’s complexity before shipping it.

The fundamentals you’ve built here are the same ones used at every level of professional software development. Keep practicing, and the patterns will become second nature.