Trees: From Representation to Advanced Patterns

Why This Section Exists: The Representation Problem

Trees don’t exist as a primitive in any programming language. You must BUILD them from the language’s primitives. JavaScript gives you objects and arrays. This section starts with the hard truth every senior engineer faces in interviews: the representation choice determines everything about your solution.

You will see the SAME tree represented three different ways in this guide, and each representation is correct—for different purposes. Understanding when and why to use each is what separates engineers who pass Google interviews from those who don’t.

Tree Fundamentals: Representation Choices

A binary tree is a structure where each node has at most two children: a left child and a right child. The three questions you must answer:

How do I represent a single node?
How do I connect nodes together?
What does "tree-shaped" input look like when Google hands it to me?

Let’s visualize a concrete example first:

This is the tree we’ll use throughout this section.

Representation 1: Node Objects (Standard for Interview Problems)

This is how you’ll represent trees in 95% of Google interview problems.

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

// Building the tree from the diagram:
const root = new TreeNode(1,
  new TreeNode(2,
    new TreeNode(4),
    new TreeNode(5)
  ),
  new TreeNode(3)
);

WHY this representation?

Flexibility: You can have any tree shape. Sparse trees, deep trees, unbalanced trees—all work.
Intuitive for recursion: The structure IS recursive. A node either is the problem (base case) or delegates to left/right subtrees (recursive case). This maps directly to your code.
What you’ll receive on LeetCode: Google will give you a string like "[1,2,3,4,5,null,null]" and expect you to parse it into this node structure.

The Tradeoff: Every node must be allocated separately. Memory overhead per node. Not suitable for dense, complete trees where array representation would be cleaner.

Representation 2: Array (Level-Order) Representation

This is how Google INPUT gives you trees. You must know how to parse it.

In a complete binary tree stored as an array:

Index 0 is the root
For node at index i:
Left child is at index 2*i + 1
Right child is at index 2*i + 2
Parent is at index floor((i - 1) / 2)

// Same tree, as array:
const treeArray = [1, 2, 3, 4, 5];

// Index:  0  1  2  3  4
// Value:  1  2  3  4  5
//
// Node 1 (index 0):
//   - left:  index 2*0+1 = 1 -> value 2
//   - right: index 2*0+2 = 2 -> value 3
//
// Node 2 (index 1):
//   - left:  index 2*1+1 = 3 -> value 4
//   - right: index 2*1+2 = 4 -> value 5
//
// Node 3 (index 2):
//   - left:  index 2*2+1 = 5 -> doesn't exist (null)
//   - right: index 2*2+2 = 6 -> doesn't exist (null)

WHY this representation?

Compact for complete trees: No pointers, just array indices. Single array stores structure and values.
Input format: LeetCode/Google gives you [1,2,3,4,5,null,null] or [1,2,3,null,null,4,5]. Know how to parse this.
Heaps rely on this: Min-heaps and max-heaps REQUIRE array representation because the complete tree property lets you use math instead of pointers.

The Tradeoff: Sparse trees are terrible. A single deep left-skewed node creates a massive array with hundreds of nulls:

// Left-skewed tree (just nodes down the left):
//       1
//      /
//     2
//    /
//   3
//
// As array: [1, 2, null, 3, null, null, null, ...]
// Positions 2, 4, 5, 6, 7, 8+ are all null!
// The array grows exponentially with depth.

Representation 3: Implicit (Never Implement—Just Know It)

Some problems (especially graph-like problems) store trees as edge lists or adjacency maps. You rarely BUILD trees this way in Google interviews, but you might parse graph input this way.

Converting Between Representations

You’ll do this constantly in interviews. Here’s how:

// Array -> TreeNode
function arrayToTree(arr) {
  if (!arr || arr.length === 0 || arr[0] === null) return null;

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

  for (let i = 1; i < arr.length; i += 2) {
    const node = queue.shift();
    if (node === null) continue;

    // Left child at index i
    if (arr[i] !== null) {
      node.left = new TreeNode(arr[i]);
      queue.push(node.left);
    }

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

  return root;
}

// TreeNode -> Array (level-order)
function treeToArray(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];

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

    if (node === null) {
      result.push(null);
    } else {
      result.push(node.val);
      queue.push(node.left);
      queue.push(node.right);
    }
  }

  // Remove trailing nulls
  while (result.length > 0 && result[result.length - 1] === null) {
    result.pop();
  }

  return result;
}

Binary Tree Traversals

Traversals are the fundamental patterns. Master these deeply—you’ll use them in almost every tree problem.

There are four main traversals. The first three are depth-first (DFS), visiting deep nodes before visiting siblings. The fourth is breadth-first (BFS), visiting level by level.

Inorder Traversal (Left, Root, Right)

Visit order: 4 → 2 → 5 → 1 → 3

Why inorder exists: For a Binary Search Tree, inorder gives you elements in sorted order.

Recursive Implementation:

function inorder(node, result = []) {
  if (node === null) return result;

  inorder(node.left, result);      // Left
  result.push(node.val);            // Root
  inorder(node.right, result);      // Right

  return result;
}

Why recursion works: The tree structure is inherently recursive. You can’t process a node until you’ve processed its left subtree. Recursion encodes this dependency automatically. The call stack becomes your worklist.

Iterative Implementation (Using Stack):

function inorderIterative(root) {
  const result = [];
  const stack = [];
  let current = root;

  while (current !== null || stack.length > 0) {
    // Go to leftmost node
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    // Current is null, pop from stack
    current = stack.pop();
    result.push(current.val);      // Visit

    // Visit right subtree
    current = current.right;
  }

  return result;
}

Why iterative?: The recursive version is elegant but can cause stack overflow on deep trees (n = 100,000 nodes). Iterative shows you understand what recursion does: it maintains a call stack. You’re doing it explicitly. Google interviewers respect this understanding.

Preorder Traversal (Root, Left, Right)

Visit order: 1 → 2 → 4 → 5 → 3

Why preorder exists:

Serialization: If you visit root first, you can reconstruct the tree from the preorder sequence alone (combined with null markers).
Copying trees: Process the node before the children—you can copy a node, then recursively copy its subtrees.
Tree structure discovery: Useful when the structure is the primary interest, not the values.

Recursive:

function preorder(node, result = []) {
  if (node === null) return result;

  result.push(node.val);            // Root
  preorder(node.left, result);      // Left
  preorder(node.right, result);     // Right

  return result;
}

Iterative:

function preorderIterative(root) {
  if (root === null) return [];

  const result = [];
  const stack = [root];

  while (stack.length > 0) {
    const node = stack.pop();
    result.push(node.val);           // Visit

    // Push right first so left is processed first (stack is LIFO)
    if (node.right !== null) stack.push(node.right);
    if (node.left !== null) stack.push(node.left);
  }

  return result;
}

Postorder Traversal (Left, Right, Root)

Visit order: 4 → 5 → 2 → 3 → 1

Why postorder exists: You process children before the parent. This is essential when you need information from the children to compute the parent’s result.

Examples: * Tree height: Can’t know a node’s height until you know its children’s heights. * Subtree sums: Can’t compute a node’s subtree sum until you sum its children’s subtrees. * Tree deletion: Delete children before the parent (otherwise, you’d lose access to children).

Recursive:

function postorder(node, result = []) {
  if (node === null) return result;

  postorder(node.left, result);     // Left
  postorder(node.right, result);    // Right
  result.push(node.val);             // Root

  return result;
}

Iterative (Two-Stack Approach):

function postorderIterative(root) {
  if (root === null) return [];

  const result = [];
  const stack1 = [root];
  const stack2 = [];

  while (stack1.length > 0) {
    const node = stack1.pop();
    stack2.push(node);

    if (node.left !== null) stack1.push(node.left);
    if (node.right !== null) stack1.push(node.right);
  }

  while (stack2.length > 0) {
    result.push(stack2.pop().val);
  }

  return result;
}

Level-Order Traversal (BFS)

Visit order: 1 → 2 → 3 → 4 → 5 (by level)

Why level-order exists:

Shortest paths: In unweighted trees, BFS finds shortest paths.
Level-by-level processing: Some problems require you to process all nodes at depth d before depth d+1.
Minimum depth: Find a leaf quickly without exploring deep branches.
Zigzag traversal: Alternate left-to-right and right-to-left per level.

Implementation (Queue-Based):

function levelOrder(root) {
  if (root === null) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);

      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }

    result.push(currentLevel);
  }

  return result;
}

Key insight: Save queue.length BEFORE the loop. As you process nodes, you add their children to the queue. If you didn’t save the length, you’d process children in the same iteration.

Binary Search Trees (BST)

A BST is not just a tree structure—it’s a data structure with an invariant: the values must satisfy a specific property at every node.

The BST Invariant

For every node: * All values in the LEFT subtree < node value * All values in the RIGHT subtree > node value

Critical: This applies to ALL descendants, not just immediate children.

// WRONG understanding:
class TreeNode {
  isValidBST_WRONG(node) {
    if (node === null) return true;

    // This only checks children, not all descendants!
    if (node.left && node.left.val >= node.val) return false;
    if (node.right && node.right.val <= node.val) return false;

    return this.isValidBST_WRONG(node.left) && this.isValidBST_WRONG(node.right);
  }
}

// Example that fails:
//       10
//      /  \
//     5   15
//    /
//   3
//  /
// 12   <- INVALID! 12 > 10, but it's in the left subtree

Search in BST

function search(root, target) {
  let current = root;

  while (current !== null) {
    if (current.val === target) return true;

    // Use the BST property to eliminate branches
    if (target < current.val) {
      current = current.left;
    } else {
      current = current.right;
    }
  }

  return false;
}

// Time: O(h) where h = height
// Best case: O(log n) if balanced
// Worst case: O(n) if degenerate (linked list)

Insert in BST

function insert(root, value) {
  if (root === null) return new TreeNode(value);

  if (value < root.val) {
    root.left = insert(root.left, value);
  } else if (value > root.val) {
    root.right = insert(root.right, value);
  }
  // If value === root.val, don't insert (handle duplicates per requirements)

  return root;
}

Delete in BST (Three Cases)

function delete(root, value) {
  if (root === null) return null;

  if (value < root.val) {
    root.left = delete(root.left, value);
  } else if (value > root.val) {
    root.right = delete(root.right, value);
  } else {
    // Found the node to delete

    // Case 1: No children (leaf node)
    if (root.left === null && root.right === null) {
      return null;
    }

    // Case 2: One child
    if (root.left === null) return root.right;
    if (root.right === null) return root.left;

    // Case 3: Two children
    // Find the inorder successor (leftmost node in right subtree)
    // OR the inorder predecessor (rightmost node in left subtree)
    let successor = root.right;
    while (successor.left !== null) {
      successor = successor.left;
    }

    root.val = successor.val;
    root.right = delete(root.right, successor.val);
  }

  return root;
}

Validate BST

This is a classic Google problem. Most solutions are wrong.

// CORRECT: Track min/max bounds for the current node
function isValidBST(node, min = -Infinity, max = Infinity) {
  if (node === null) return true;

  // Check if current node violates the invariant
  if (node.val <= min || node.val >= max) return false;

  // Recursively check subtrees with tighter bounds
  return (
    isValidBST(node.left, min, node.val) &&
    isValidBST(node.right, node.val, max)
  );
}

// Why this works:
// - When checking the left subtree, all values must be < node.val
//   So the new max becomes node.val
// - When checking the right subtree, all values must be > node.val
//   So the new min becomes node.val
// - This tracks the CONSTRAINT that each subtree must satisfy

Balanced Trees (Conceptual)

Google rarely asks you to implement AVL or Red-Black trees. They assume you know they exist.

What they guarantee: After insertion or deletion, the height is O(log n).

Why this matters: An unbalanced BST degenerates into a linked list (h = n). Search becomes O(n) instead of O(log n).

What you should know:

AVL trees: Self-balancing via rotations. Stricter balance (heights of left/right subtrees differ by at most 1). Higher overhead but guaranteed O(log n) operations.
Red-Black trees: Relaxed balance (no strict height constraint, but clever color rules ensure O(log n)). Lower overhead, used in real systems (Java’s TreeMap, C++ std::map).

If asked in an interview: "Red-Black trees use coloring and rotation invariants to guarantee O(log n) height while minimizing rebalancing overhead. I won’t implement it here, but the idea is that color rules ensure no path from root to leaf is more than twice as long as any other path."

Common Tree Problems for Google

Problem 1: Maximum Depth of Binary Tree

Statement: Given a binary tree, return its maximum depth (number of nodes on the longest path from root to leaf).

Approach: Postorder traversal. You need children’s depths before computing the parent’s depth.

function maxDepth(node) {
  if (node === null) return 0;

  const leftDepth = maxDepth(node.left);
  const rightDepth = maxDepth(node.right);

  return Math.max(leftDepth, rightDepth) + 1;
}

// Time: O(n) - visit every node once
// Space: O(h) - recursion stack depth

Problem 2: Invert Binary Tree

Statement: Swap left and right children for every node.

Approach: Preorder. Process the node (swap children), then recurse.

function invertTree(node) {
  if (node === null) return null;

  // Swap children first
  const temp = node.left;
  node.left = node.right;
  node.right = temp;

  // Then invert subtrees
  invertTree(node.left);
  invertTree(node.right);

  return node;
}

// Time: O(n)
// Space: O(h)

Problem 3: Validate BST

Already covered above. Remember: track min/max bounds.

Problem 4: Lowest Common Ancestor (LCA)

Statement: Given a BST and two nodes p and q, find their lowest common ancestor (deepest node that is an ancestor of both).

Approach: For BST, use the ordering property. The LCA is where the paths diverge.

function lowestCommonAncestor(root, p, q) {
  // Assume p.val < q.val for clarity
  const smaller = Math.min(p.val, q.val);
  const larger = Math.max(p.val, q.val);

  let current = root;

  while (current !== null) {
    if (current.val < smaller) {
      // Both p and q are in the right subtree
      current = current.right;
    } else if (current.val > larger) {
      // Both p and q are in the left subtree
      current = current.left;
    } else {
      // current.val is between smaller and larger
      // Or current is one of the nodes
      return current;
    }
  }

  return null;
}

// Time: O(log n) for balanced, O(n) for degenerate
// Space: O(1) - no recursion

Problem 5: Serialize and Deserialize Binary Tree

Statement: Design an algorithm to serialize and deserialize a binary tree.

Approach: Preorder traversal with null markers. Preorder is chosen because you can reconstruct the tree from preorder alone.

function serialize(root) {
  const result = [];

  function preorder(node) {
    if (node === null) {
      result.push('null');
      return;
    }

    result.push(String(node.val));
    preorder(node.left);
    preorder(node.right);
  }

  preorder(root);
  return result.join(',');
}

function deserialize(data) {
  const nodes = data.split(',');
  let index = 0;

  function buildTree() {
    if (index >= nodes.length || nodes[index] === 'null') {
      index++;
      return null;
    }

    const node = new TreeNode(parseInt(nodes[index]));
    index++;

    node.left = buildTree();
    node.right = buildTree();

    return node;
  }

  return buildTree();
}

// Example:
// Tree: [1, 2, 3] (with implicit nulls)
// Serialized: "1,2,null,null,3,null,null"
// This is valid input for deserialize to reconstruct the original tree

Problem 6: Binary Tree Level Order Traversal

Already covered in traversals section. Key: save levelSize before processing.

Problem 7: Kth Smallest Element in BST

Statement: Given a BST and integer k, return the kth smallest element.

Approach: Inorder traversal gives sorted order. Count until k.

function kthSmallest(root, k) {
  let count = 0;
  let result = null;

  function inorder(node) {
    if (node === null || result !== null) return;

    inorder(node.left);

    count++;
    if (count === k) {
      result = node.val;
      return;
    }

    inorder(node.right);
  }

  inorder(root);
  return result;
}

// Time: O(k) - stop as soon as we find the kth element
// Space: O(h)

Tries (Prefix Trees)

A Trie is a tree where each node represents a CHARACTER, and paths from root to marked nodes form WORDS.

Why Tries Exist

Problem: You have 10,000 words. You want to check if a string is in the set.

Hash set: O(1) lookup on average, but word length L matters for hashing.
Sorted array + binary search: O(log n * L) where n = number of words.
Trie: O(L) lookup, ALWAYS. Doesn’t matter how many words you’ve stored. Also supports prefix matching.

class TrieNode {
  constructor() {
    this.children = new Map();  // or new Array(26) for lowercase English
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;

    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }

    node.isEndOfWord = true;
  }

  search(word) {
    const node = this._findNode(word);
    return node !== null && node.isEndOfWord;
  }

  startsWith(prefix) {
    return this._findNode(prefix) !== null;
  }

  _findNode(prefix) {
    let node = this.root;

    for (const char of prefix) {
      if (!node.children.has(char)) {
        return null;
      }
      node = node.children.get(char);
    }

    return node;
  }
}

// Example:
const trie = new Trie();
trie.insert("apple");
trie.insert("app");
console.log(trie.search("apple"));    // true
console.log(trie.search("app"));      // true
console.log(trie.search("appl"));     // false
console.log(trie.startsWith("app"));  // true

Problem: Word Search II

Statement: Given a 2D grid and a list of words, find all words that exist in the grid. A word is formed by connecting adjacent cells (horizontally or vertically), and each cell can be used at most once per word.

Approach: Build a Trie of all words. Then DFS on the grid, using the Trie to prune branches.

function findWords(board, words) {
  const trie = new Trie();
  for (const word of words) {
    trie.insert(word);
  }

  const result = new Set();

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      dfs(board, i, j, trie.root, "", result);
    }
  }

  return Array.from(result);
}

function dfs(board, i, j, trieNode, path, result) {
  if (i < 0 || i >= board.length || j < 0 || j >= board[i].length) {
    return;
  }

  const char = board[i][j];

  // If cell is marked as visited or not in trie, stop
  if (char === '#' || !trieNode.children.has(char)) {
    return;
  }

  trieNode = trieNode.children.get(char);
  path += char;

  if (trieNode.isEndOfWord) {
    result.add(path);
  }

  // Mark as visited
  board[i][j] = '#';

  // Explore neighbors
  dfs(board, i + 1, j, trieNode, path, result);
  dfs(board, i - 1, j, trieNode, path, result);
  dfs(board, i, j + 1, trieNode, path, result);
  dfs(board, i, j - 1, trieNode, path, result);

  // Unmark
  board[i][j] = char;
}

Heaps and Priority Queues

A heap is a complete binary tree stored as an array that maintains a HEAP PROPERTY: every parent is ⇐ all children (min-heap) or >= all children (max-heap).

Why Array Representation for Heaps

Heaps MUST be complete trees (all levels filled except possibly the last, which is left-justified). This means there are NO GAPS. You can store a complete tree as an array without wasting space.

For parent at index i: * Left child: 2i + 1 * Right child: 2i + 2 * Parent: floor((i - 1) / 2)

MinHeap Implementation

class MinHeap {
  constructor() {
    this.heap = [];
  }

  insert(value) {
    this.heap.push(value);
    this._bubbleUp(this.heap.length - 1);
  }

  _bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);

      if (this.heap[index] < this.heap[parentIndex]) {
        [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  extractMin() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this._bubbleDown(0);

    return min;
  }

  _bubbleDown(index) {
    while (true) {
      let smallest = index;
      const left = 2 * index + 1;
      const right = 2 * index + 2;

      if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
        smallest = left;
      }

      if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
        smallest = right;
      }

      if (smallest !== index) {
        [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
        index = smallest;
      } else {
        break;
      }
    }
  }

  peek() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

  size() {
    return this.heap.length;
  }
}

// Time complexity:
// insert: O(log n) - bubble up
// extractMin: O(log n) - bubble down
// peek: O(1)

Problem 1: Kth Largest Element

Statement: Find the kth largest element in an array.

Approach: Use a min-heap of size k. The smallest element in the heap is the kth largest in the array.

function findKthLargest(nums, k) {
  const minHeap = new MinHeap();

  for (const num of nums) {
    minHeap.insert(num);

    // Keep heap size at k
    if (minHeap.size() > k) {
      minHeap.extractMin();
    }
  }

  return minHeap.peek();
}

// Example: [3, 2, 1, 5, 6, 4], k = 2
// Sorted descending: [6, 5, 4, 3, 2, 1]
// Kth largest = 5
//
// Heap tracking:
// - Process 3: heap = [3]
// - Process 2: heap = [2, 3]
// - Process 1: heap = [1, 2, 3], size > k, extract min -> heap = [2, 3]
// - Process 5: heap = [2, 3, 5]
// - Process 6: heap = [2, 3, 5, 6], size > k, extract min -> heap = [3, 5, 6]
// - Process 4: heap = [3, 5, 6, 4], size > k, extract min -> heap = [4, 5, 6]
// Result: peek = 5

// Time: O(n log k)
// Space: O(k)

Problem 2: Merge K Sorted Lists

Statement: Merge k sorted linked lists into one sorted list.

Approach: Use a min-heap. Track the head of each list and always process the smallest element.

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeKLists(lists) {
  // Min-heap comparing by node value
  const minHeap = new MinHeap();

  // Insert the head of each list
  for (const list of lists) {
    if (list !== null) {
      minHeap.insert({ node: list, val: list.val });
    }
  }

  const dummy = new ListNode(0);
  let current = dummy;

  while (minHeap.size() > 0) {
    const { node } = minHeap.extractMin();
    current.next = node;
    current = current.next;

    if (node.next !== null) {
      minHeap.insert({ node: node.next, val: node.next.val });
    }
  }

  return dummy.next;
}

// Issue with above: MinHeap compares objects, not values.
// Better approach: store [val, listIndex, node] tuple or implement a comparator.
// For the interview, mention: "I'll assume a MinHeap that accepts a comparator function."

In a real Google interview, you don’t need to implement a heap. You can say: "I’ll use a MinHeap implementation that has insert and extractMin methods. In Python, that’s heapq. In JS, I’d implement it or use a library." Interviewers understand you’re not memorizing heap code—they want to see you know when to use it.

Summary: When to Use What

Pattern	When to Use	Time Complexity
Inorder	Sorted order from BST, validation	O(n)
Preorder	Serialization, tree copying	O(n)
Postorder	Subtree results, tree height	O(n)
Level-order (BFS)	Min depth, right side view, level-by-level	O(n)
BST Operations	Sorted data with insertion/deletion	O(log n) if balanced, O(n) if degenerate
Trie	Prefix matching, word searches	O(L) where L = word length
Heap	Kth largest, top k elements, priority queue	O(log n) per operation

Pattern

When to Use

Time Complexity

Inorder

Sorted order from BST, validation

O(n)

Preorder

Serialization, tree copying

O(n)

Postorder

Subtree results, tree height

O(n)

Level-order (BFS)

Min depth, right side view, level-by-level

O(n)

BST Operations

Sorted data with insertion/deletion

O(log n) if balanced, O(n) if degenerate

Trie

Prefix matching, word searches

O(L) where L = word length

Heap

Kth largest, top k elements, priority queue

O(log n) per operation