Introduction to Trees

A tree is a collection of nodes connected by directed edges where one designated node — the root — has no parent, and every other node has exactly one parent. Because of that constraint there are no cycles, and the structure naturally models hierarchy: file systems, HTML DOM, company org charts, and expression evaluators all use trees.

Core Vocabulary

Every node in a tree plays one or more roles:

• Root — the single top-level node with no parent.
• Parent — a node that has at least one child.
• Child — a node directly connected below its parent.
• Leaf — a node with no children.
• Subtree — any node plus all of its descendants.

//          A          <-- root
//        /   \
//       B     C       <-- children of A; siblings of each other
//      / \     \
//     D   E     F     <-- D, E, F are leaves

// Node A is the parent of B and C.
// Node B is the parent of D and E.
// Node C is the parent of F.

Depth and Height

Depth is measured from the root downward. The root itself has depth 0. Each edge you cross adds 1.

Height is measured from a node upward to its farthest leaf. A leaf has height 0. The height of the tree equals the height of the root.

function depth(node, target, d = 0) {
  if (!node) return -1;
  if (node === target) return d;
  return depth(node.left, target, d + 1) !== -1
    ? depth(node.left, target, d + 1)
    : depth(node.right, target, d + 1);
}

function height(node) {
  if (!node) return -1;           // empty tree has height -1
  return 1 + Math.max(height(node.left), height(node.right));
}

The height of the example tree above is 2 (from A down to D, E, or F).

Tree vs Graph

A tree is a special case of a directed acyclic graph (DAG) with the added constraint that every non-root node has exactly one parent. Relax either constraint and you have a general graph:

• Allow a node to have two parents → DAG, but no longer a tree.
• Allow a back-edge (child pointing to ancestor) → a cycle → a general graph.

Because trees are graphs, all graph algorithms apply to them — but trees also admit simpler, more efficient algorithms that exploit the single-parent guarantee.

How Nodes Are Linked

The classic linked representation attaches child references directly to each node object. A generic tree might store an array of children; a binary tree (next lesson) stores exactly left and right. This linked approach makes insertion anywhere cheap and the structure easy to visualize in code.

class TreeNode {
  constructor(val = 0, children = []) {
    this.val = val;
    this.children = children;
  }
}

const root = new TreeNode("A", [
  new TreeNode("B", [new TreeNode("D"), new TreeNode("E")]),
  new TreeNode("C", [new TreeNode("F")]),
]);

Up Next

Binary trees restrict each node to at most two children, unlocking a rich set of algorithms. The next lesson covers how they are structured and stored.