← Index

Trees & Heaps

Tree (General)

A hierarchy — one root, any number of children per node.

What it is

A general tree is any hierarchy: one root node, and each node can have any number of children (no ordering rule, no cap of 2 like a Binary Search Tree). It's the shape underneath most nested UI and nested data you deal with day to day.

Real-world examples

• An org chart — one CEO at the root, managers branching below, each with their own reports.
• A folder/file system — a directory can contain any number of files or subdirectories.

Where you've probably used this already

• The DOM itself — every element is a node with any number of children, walked via parentNode/children exactly like this.
• Rendering nested comment threads or nested menus/categories in a UI.
• Recursively resolving a nested JSON config, or walking a directory tree with fs.readdir.

Complexity

Code

// Tree — a general hierarchy: one root, each node can have any number
// of children (unlike a Binary Search Tree, which caps it at 2 and
// enforces ordering). Think folder structures, org charts, comment threads.

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  addChild(value) {
    const child = new TreeNode(value);
    this.children.push(child);
    return child;
  }
}

// Depth-First traversal — go as deep as possible before backtracking
function depthFirst(node, depth = 0, out = []) {
  out.push("  ".repeat(depth) + node.value);
  for (const child of node.children) {
    depthFirst(child, depth + 1, out);
  }
  return out;
}

// Breadth-First traversal — go level by level, using a queue
function breadthFirst(root) {
  const result = [];
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    result.push(node.value);
    queue.push(...node.children);
  }
  return result;
}

// --- Example Usage: a file system tree ---
const root = new TreeNode("root");
const src = root.addChild("src");
const docs = root.addChild("docs");
src.addChild("index.js");
src.addChild("utils.js");
docs.addChild("README.md");

console.log("Depth-first (indented):\n" + depthFirst(root).join("\n"));
// root
//   src
//     index.js
//     utils.js
//   docs
//     README.md

console.log("Breadth-first:", breadthFirst(root));
// ["root", "src", "docs", "index.js", "utils.js", "README.md"]

// This exact shape is what you're walking every time you:
// - render nested comments/replies
// - traverse the DOM (parentNode / children)
// - resolve a nested JSON config or a file directory