Trees, tries, and traversal order

Trees are everywhere you look once you know the shape: the DOM, the file system, a JSON document, a company org chart, the syntax tree your compiler builds from your code. This page covers the tree vocabulary, the four ways to walk one, the binary search tree that keeps data sorted, and the trie that makes autocomplete fast.

The problem it solves

Some data is naturally hierarchical: a folder contains folders and files, a comment has replies which have replies, a page has nested components. A linear structure forces you to flatten that hierarchy and lose it. A tree keeps it, and adds a second benefit: when the tree is organised by a rule (smaller values on the left, larger on the right), you can discard half of the remaining data at every step, the way binary search does on a sorted array, but on data that supports fast insertion.

Structure and vocabulary

• Root: the one node with no parent.
• Leaf: a node with no children.
• Parent, child, sibling: relationships along the edges.
• Depth of a node: edges from the root to it. The root has depth 0.
• Height of a tree: the number of edges on the longest root-to-leaf path. Most tree performance is really about height.
• Subtree: any node together with everything below it. Nearly every tree algorithm is recursion on subtrees.
• Binary tree: every node has at most two children, called left and right.

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

A tree is a linked list whose nodes can point at more than one next node. A linked list has one obvious "next"; from a tree node you can go left, right or nowhere, and that branching is what makes "in what order do I visit things?" a real question.

The four traversal orders

Every algorithm that touches all the nodes must pick an order. For the tree above:

The first three are depth-first: they follow one branch all the way down before backing up. They are naturally recursive, because the call stack remembers where to come back to.

function inOrder(node, visit) {
  if (node === null) return;
  inOrder(node.left, visit);
  visit(node.val);
  inOrder(node.right, visit);
}

// The same walk without recursion: the explicit stack replaces the call stack.
function inOrderIterative(root) {
  const out = [];
  const stack = [];
  let cur = root;
  while (cur !== null || stack.length > 0) {
    while (cur !== null) { stack.push(cur); cur = cur.left; }
    cur = stack.pop();
    out.push(cur.val);
    cur = cur.right;
  }
  return out;
}

Pre-order and post-order differ only in where the visit line sits relative to the two recursive calls.

Breadth-first: level by level with a queue

Level-order is breadth-first: everything at depth 1 before anything at depth 2. The difference from depth-first is entirely which structure remembers "what to visit next": a stack gives depth-first, a queue gives breadth-first.

function levelOrder(root) {
  if (root === null) return [];
  const levels = [];
  const queue = [root];
  while (queue.length > 0) {
    const width = queue.length;      // snapshot: exactly this level's nodes
    const level = [];
    for (let i = 0; i < width; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left)  queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    levels.push(level);
  }
  return levels;
}

Snapshotting queue.length before the inner loop is the one line that turns "visit everything eventually" into "visit level by level". Without it you still visit every node, but you cannot tell where one level ends and the next begins.

Recursion on subtrees: the tree-problem template

Most tree problems are the same three steps: handle null, recurse on the left and right, combine the results.

function height(node: TreeNode | null): number {
  if (node === null) return -1;                    // an empty tree has height -1, a leaf 0
  return 1 + Math.max(height(node.left), height(node.right));
}

Swap the combining step and you get node count, "is the tree balanced", the diameter, the sum along a path, or whether two trees are identical. When a problem says "tree", try this template first.

Binary search trees: sorted, as a shape

A binary search tree (BST) adds one rule: for every node, everything in its left subtree is smaller and everything in its right subtree is larger. That rule turns search into a series of one-way decisions.

class BST {
  root = null;

  insert(val) {
    const node = new TreeNode(val);
    if (this.root === null) { this.root = node; return; }
    let cur = this.root;
    while (true) {
      if (val < cur.val) {
        if (cur.left === null) { cur.left = node; return; }
        cur = cur.left;
      } else {
        if (cur.right === null) { cur.right = node; return; }
        cur = cur.right;
      }
    }
  }

  has(val) {
    let cur = this.root;
    while (cur !== null) {
      if (val === cur.val) return true;
      cur = val < cur.val ? cur.left : cur.right;
    }
    return false;
  }
}

Search, insert and delete are all O(h), where h is the height. Deleting has three cases: a leaf (just remove it), a node with one child (replace it with that child), and a node with two children (replace its value with its in-order successor, the smallest value in the right subtree, then delete that successor instead).

The catch: balance

h is only log n when the tree is roughly balanced. Insert already-sorted data into a plain BST and every node gets exactly one child: you have built a linked list with a tree's interface, and every operation degrades to O(n). Self-balancing trees (AVL trees, red-black trees) rotate nodes after each change to guarantee log n height whatever the insertion order. A plain BST makes no such promise, so real systems use the self-balancing kind.

Validating a BST, the classic trap

"Is this tree a valid BST?" is asked constantly, and the tempting answer is wrong. Checking only node.left.val < node.val < node.right.val passes trees where a value deep in the right subtree is smaller than the root. The rule is about the whole subtree, so carry a (min, max) window down the recursion:

function isValidBST(node: TreeNode | null, min = -Infinity, max = Infinity): boolean {
  if (node === null) return true;
  if (node.val <= min || node.val >= max) return false;
  return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
}

An equivalent trick: an in-order traversal of a valid BST is strictly increasing, so check that.

Tries: trees keyed by character, not by comparison

A trie (prefix tree) restructures the idea. Instead of "smaller goes left", each edge is a single character, and the path from the root spells out a string.

Inserting "cat", "care" and "dog" shares the c-a path between the first two, and that sharing is the entire point. Asking "does anything start with ca?" is "walk two edges and see if you fall off the trie", which costs O(length of the prefix), no matter how many words are stored.

class Trie {
  root = {};

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node['$'] = true;              // end-of-word marker
  }

  #walk(text) {
    let node = this.root;
    for (const ch of text) {
      node = node[ch];
      if (!node) return null;
    }
    return node;
  }

  search(word)     { return this.#walk(word)?.['$'] === true; }
  startsWith(text) { return this.#walk(text) !== null; }
}

Two details worth saying out loud. The end-of-word marker matters: without it, search("ca") would wrongly succeed after inserting "cat", because ca is only a prefix. And the trie trades memory for speed: one node per distinct prefix character can add up, so production tries compress single-child chains (a radix tree).

Where trees are used in real systems

Trees you already use

• The DOM. document.body is a root. querySelector and getElementsByTagName do depth-first walks, and children and parentNode are tree edges.
• React. JSX becomes a tree of elements, and reconciliation compares two trees.
• Your file system and `git`. A commit points to a tree object which points to subtrees and blobs.
• Your database index. The B-tree behind almost every CREATE INDEX.

When a tree beats a hash table, and when it does not

A hash table gives O(1) lookup but discards order: iterating it yields no useful sequence. A balanced BST gives up that O(1) for O(log n), in exchange for keeping everything sorted. In-order traversal walks every key from smallest to largest for free, and range queries ("everything between 10 and 50") are a bounded walk instead of a full scan.

When not to use a tree

• You only need membership. A hash table is simpler and faster.
• The data is sorted once and never changes. A sorted array with binary search is more compact and cache-friendly.
• You are building a plain BST from sorted or nearly sorted input. It degenerates into a list. Use a self-balancing tree or shuffle first.
• The data is not really hierarchical. If nodes can have several parents or form cycles, you have a graph, not a tree.

What interviewers ask

• "Implement the four traversals, recursively and iteratively." And which one gives sorted output on a BST.
• "Level-order traversal." A queue, and the snapshot of the level width.
• "Validate a binary search tree." The min and max window, and why a parent-child check is wrong.
• "Lowest common ancestor." On a BST, walk down until the two values split to different sides.
• "Height, diameter, is it balanced?" The recursion template.
• "What is the complexity of BST search?" O(h): log n balanced, n worst case. Say both.
• "Implement a trie with insert, search and startsWith." And why you need the end-of-word marker.
• "Serialise and deserialise a tree." Pre-order with null markers, or level-order.

The mistake to avoid

Confusing a binary tree with a binary search tree, and validating only parent against child. A binary tree has no ordering rule; a BST's rule applies to whole subtrees. The second mistake to avoid is quoting "O(log n)" for a BST without saying "if it is balanced": the honest answer is O(h), and h can be n.

A tree is a graph with no cycles and a designated root. Everything on this page (recursion on subtrees, depth-first with a stack, breadth-first with a queue) carries over to graphs, with one extra job: remembering which nodes you have already visited.