Trees

A hierarchical data structure with a root node and child nodes. Binary Search Trees (BSTs) are a common type for efficient searching.

What is it?

Trees are used to represent hierarchical data. The file system on your Mac or Windows computer is a perfect example. You have a root directory (like C:), which contains child folders and files. Each folder can contain more folders and files, forming a tree structure. Another key example is the HTML DOM that web browsers use to render pages. The <html> element is the root node, with <head> and <body> as its children. This hierarchical structure allows browsers to efficiently render content and lets developers manipulate specific page elements with JavaScript. Specialized trees like Binary Search Trees (BSTs) are optimized for fast searching (O(log n)), making them ideal for database indexing.

Time Complexity

AccessO(log n)

SearchO(log n)

InsertionO(log n)

DeletionO(log n)

Implementation Example

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

// Simple Binary Search Tree insert
function insert(node, value) {
  if (node === null) {
    return new TreeNode(value);
  }
  if (value < node.value) {
    node.left = insert(node.left, value);
  } else {
    node.right = insert(node.right, value);
  }
  return node;
}

Trees

Trees Deep Dive

Trees encode hierarchy, enabling logarithmic operations for ordered data and expressive modeling for documents, files, and scene graphs.

?But why does this matter?

Balancing strategy (AVL, Red-Black, B-Tree) determines whether a tree excels at reads, writes, or cache friendliness.

Visual Flow

How it actually moves

Search (balanced BST)

O(log n)

Navigates left/right branches based on ordering.

Insertion

O(log n)

Places value then rebalances/rotates if needed.

Traversal

O(n)

DFS or BFS visits each node once for aggregation.

Compute binary tree height + balance check

Define a recursive helper that returns the height of a subtree.

If node is null, return 0.

Recursively compute leftHeight and rightHeight.

If |leftHeight - rightHeight| > 1, mark the tree as unbalanced.

Return max(leftHeight, rightHeight) + 1 to account for the current node.

Interview variations include “is the tree balanced?”, “what is the diameter?”, or “what level has the most nodes.”

Watch the best explainer

Binary Tree Algorithms for Technical Interviews — Full Course

freeCodeCamp · Alvin Zablan

Top-rated interview-focused tree course: traversals, sums, paths — with animations.

Binary trees as family trees

Every parent branches into children, and the “height” tells you how many generations exist. A balanced family tree grows evenly on both sides; an unbalanced one becomes a long chain that’s harder to navigate.

Real-world analogy

Routing tables mirror this idea: left branches handle traffic for smaller IP ranges, right branches for larger ones.

Takeaway

Keeping tree height logarithmic ensures every lookup inspects only a handful of levels.

Practical applications

• Filesystem directories and package dependency graphs.
• Database indexes (B+ trees) that keep disk seeks predictable.
• UI layout trees (DOM, accessibility trees) for rendering pipelines.

Technical insights

• Self-balancing trees rebalance via rotations to guarantee O(log n) height.
• B-Trees pack multiple keys per node to align with disk/page sizes.
• Persistent trees share structure between versions, enabling time-travel debugging.

When to reach for it

• Hierarchical data
• Range queries
• Autocompletion tries

Operations Breakdown

Search (balanced BST)

O(log n)

Navigates left/right branches based on ordering.

Insertion

O(log n)

Places value then rebalances/rotates if needed.

Traversal

O(n)

DFS or BFS visits each node once for aggregation.

Best practices

• Pick an ordering that matches query patterns to minimize traversals.
• Batch inserts then rebalance to avoid oscillating rotations.
• Profile tree height and distribution in production traffic to catch skew.

Common pitfalls

• Allowing duplicates without tie-breakers causes infinite loops.
• Recursive traversals on very deep trees can overflow the stack; prefer iterative with explicit stack.
• Neglecting delete balancing turns O(log n) structure into a linked list over time.

Every kind of Trees

Interviewers rarely say which flavor they mean — they expect you to recognize it from the problem. Each variant below comes with the algorithms it unlocks.

Type 1 of 7

Binary Tree

→ full page

Each node has at most two children. No ordering guarantee — the value is in the shape, and traversal order is the main tool.

What to know

Preorder copies structure, inorder is meaningful mostly for BSTs, postorder deletes safely, level-order uses BFS.
Height, diameter, and balance checks are all postorder computations.
Serialization (preorder + null markers) round-trips any binary tree.

Algorithms to reach for

Four traversals (pre/in/post/level)

O(n)

Visit orders for copying, evaluating, deleting, printing

Diameter via postorder

O(n)

Longest node-to-node path (LeetCode 543)

LCA in a binary tree

O(n)

Lowest common ancestor without parent pointers (LeetCode 236)

Serialize/deserialize

O(n)

Ship trees across a network (LeetCode 297)

In the wild: Expression trees in compilers, decision trees, DOM subtrees, Huffman code trees.

Practice problems — hints, approach & solution on their own pages

Diameter of Binary TreeEasy Lowest Common Ancestor of a Binary TreeMedium Serialize and Deserialize Binary TreeHard

Type 2 of 7

Binary Search Tree (BST)

→ full page

Left < node < right, recursively. Inorder traversal yields sorted order — that single fact powers most BST interview questions.

What to know

All operations are O(h); h is log n only if the tree stays balanced.
Validation needs min/max bounds passed down, not just parent-child checks.
Delete has three cases; the two-children case swaps in the inorder successor.
Sorted-order problems (kth smallest, closest value, range sums) fall to inorder walks.

Algorithms to reach for

Search / insert / delete

O(h)

Ordered dictionary operations

Validate BST with bounds

O(n)

Confirm the global invariant (LeetCode 98)

Kth smallest via inorder

O(h + k)

Order statistics without full sort (LeetCode 230)

In the wild: In-memory ordered maps, database index prototypes, autocompletion rankers.

Practice problems — hints, approach & solution on their own pages

Validate Binary Search TreeMedium Kth Smallest Element in a BSTMedium Delete Node in a BSTMedium

Type 3 of 7

Self-Balancing Trees (AVL / Red-Black)

→ full page

BSTs that rotate on write to keep height O(log n) no matter the insertion order. The fix for the sorted-input worst case.

What to know

AVL balances harder (height diff ≤ 1): faster reads, more rotation work on writes.
Red-black relaxes balance for cheaper writes — the standard library default.
Full mechanics live in the Red-Black Trees deep dive.

Algorithms to reach for

Rotations (LL/RR/LR/RL)

O(1) each

Local O(1) rebalancing after insert/delete

Guaranteed O(log n) ops

O(log n)

Ordered map/set without degeneration

In the wild: C++ std::map, Java TreeMap, Linux CFS scheduler, epoll timers.

Practice problems — hints, approach & solution on their own pages

Balanced Binary TreeEasy Convert Sorted Array to Binary Search TreeEasy Balance a Binary Search TreeMedium

Type 4 of 7

N-ary Tree

→ full page

Any number of children per node. File systems, org charts, and UI component trees are all n-ary.

What to know

Children live in a list; traversals loop over it instead of left/right.
DFS maps to recursive directory walks; BFS maps to org-chart levels.
Left-child/right-sibling encoding converts any n-ary tree to binary.

Algorithms to reach for

N-ary DFS/BFS

O(n)

Walk file systems, render component trees

Left-child right-sibling encoding

O(n)

Represent n-ary as binary

In the wild: File explorers, React/DOM trees, comment threads, category taxonomies.

Practice problems — hints, approach & solution on their own pages

Maximum Depth of N-ary TreeEasy N-ary Tree Level Order TraversalMedium

Type 5 of 7

Trie (Prefix Tree)

→ full page

A tree keyed by characters: one path per prefix. Lookup cost depends on key length, not on how many keys are stored.

What to know

Each node holds children (map or 26-array) plus an end-of-word flag.
Autocomplete = walk to the prefix node, then DFS the subtree.
Word Search II pairs a trie with grid DFS to prune dead branches early.

Algorithms to reach for

Insert / search / startsWith

O(L)

Prefix dictionary ops (LeetCode 208)

Wildcard search with DFS

O(26^dots · L)

Match "." patterns (LeetCode 211)

Trie + grid DFS

prunes hard

Find many words in a letter grid (LeetCode 212)

In the wild: Search-box autocomplete, spell checkers, IP routing (radix tries), T9 input.

Practice problems — hints, approach & solution on their own pages

Implement Trie (Prefix Tree)Medium Design Add and Search Words Data StructureMedium Word Search IIHard

Type 6 of 7

Segment Tree & Fenwick Tree (BIT)

→ full page

Range-query machines: answer "sum/min/max over [l, r]" and update single points, both in O(log n).

What to know

Segment tree: each node covers an interval; queries stitch O(log n) disjoint nodes.
Fenwick tree does prefix sums in ~10 lines using low-bit index jumps.
Lazy propagation extends segment trees to range updates.
Choose Fenwick for sums; segment tree for min/max/custom merges.

Algorithms to reach for

Segment tree query/update

O(log n)

Range aggregates with point updates

Lazy propagation

O(log n)

Range updates deferred until needed

Fenwick prefix sums

O(log n)

Count smaller after self, inversions

In the wild: Leaderboard rank queries, time-series rollups, computational geometry sweeps.

Practice problems — hints, approach & solution on their own pages

Range Sum Query — MutableMedium Count of Smaller Numbers After SelfHard

Type 7 of 7

B-Tree / B+ Tree

→ full page

Wide, shallow trees storing hundreds of keys per node — designed so each node is one disk page. The tree behind almost every database.

What to know

High fanout means height 3–4 even for billions of keys.
B+ trees keep values only in leaves and chain leaves for fast range scans.
Nodes split when full and merge when underfull, staying balanced.

Algorithms to reach for

B-tree search/insert/split

O(log_B n)

Disk-friendly ordered storage

B+ leaf-chain range scan

O(log_B n + k)

BETWEEN queries without re-descending

In the wild: MySQL InnoDB, PostgreSQL, SQLite indexes, filesystems (NTFS, ext4, APFS).

Signature algorithms

Algorithm

Inorder DFS (BST search)

Visit left subtree, node, then right subtree to read values in sorted order on a binary search tree.

Time

O(n)

Space

O(h)

function inorder(node, output = []) {
  if (!node) return output;
  inorder(node.left, output);
  output.push(node.value);
  inorder(node.right, output);
  return output;
}

Algorithm

Level-order traversal

Breadth-first search that walks the tree layer by layer, useful for shortest path in unweighted trees.

Time

O(n)

Space

O(w)

function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  while (queue.length) {
    const size = queue.length;
    const level = [];
    for (let i = 0; i < size; i += 1) {
      const node = queue.shift();
      level.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

Algorithm

Lowest common ancestor (binary tree)

Return the deepest node that is an ancestor of both targets—common interview staple.

Time

O(n)

Space

O(h)

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) {
    return root;
  }
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ?? right;
}

Pseudo Code • Compute binary tree height + balance check

Flow Diagram

Define a recursive helper that returns the height of a subtree.
If node is null, return 0.
Recursively compute leftHeight and rightHeight.
If |leftHeight - rightHeight| > 1, mark the tree as unbalanced.
Return max(leftHeight, rightHeight) + 1 to account for the current node.

Interview variations include “is the tree balanced?”, “what is the diameter?”, or “what level has the most nodes.”

Hands-on code

Compare how the same idea looks in JavaScript, Python, and Go.

function isBalanced(root) {
  let balanced = true;

  function height(node) {
    if (!node) return 0;
    const left = height(node.left);
    const right = height(node.right);
    if (Math.abs(left - right) > 1) balanced = false;
    return Math.max(left, right) + 1;
  }

  height(root);
  return balanced;
}