What is the height of a tree?

AlgorithmsJunior~3 min read

Short answer

The height of a tree is the length (in edges) of the longest path from the root to a leaf.

A single-node tree: height 0 (counting in edges).
An empty tree: height -1 (counting in edges).
Height is sometimes counted in nodes instead: then a single node is 1, and an empty tree is 0.

Detailed answer

Definition and conventions

There are two common conventions for counting height:

In edges (very common in practice): height is the number of edges on the longest path from the root to a leaf. Then: an empty tree is -1; a leaf is 0; a single-node tree is 0.
In nodes: height is the number of nodes on that path. Then: an empty tree is 0; a leaf is 1; a single-node tree is 1.

Converting between conventions: h_nodes = h_edges + 1; h_edges = h_nodes - 1. From here on we default to the edges definition.

Depth of a node: the number of edges from the root to that node.
Level of a node: sometimes the same as depth (but can also be counted in nodes). Clarify this in an interview.
Height of a node: the height of the subtree rooted at that node (analogous to a tree's height). A tree's height = the height of its root node.

Example trees

text

Example 1 (in edges):

A
├─ B
│  └─ D
└─ C

Longest path: A → B → D (2 edges), so the height = 2.

If counted in nodes, the height would be 3.

text

Example 2 (a chain of 4 nodes):

1
└─ 2
   └─ 3
      └─ 4

The longest path contains 3 edges, so the height = 3.

Formula and properties

Recurrence (in edges): h(∅) = -1; h(leaf) = 0; h(v) = 1 + max(h(children of v)). No children means a leaf.
Bounds for a tree of n nodes: 0 ≤ h ≤ n - 1 (in edges). Minimum height is achieved by a "nearly complete" tree, maximum by a chain.
For a nearly complete binary tree: h ≈ ⌊log2 n⌋ (in edges). For a chain: h = n - 1.
Converting conventions: h_nodes = h_edges + 1; h_edges = h_nodes - 1.

How to compute it in practice

Recursive DFS (binary tree, JS)

javascript

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

// Height in edges: an empty tree is -1, a leaf is 0
function heightBinary(root) {
  if (root === null) return -1;
  return 1 + Math.max(heightBinary(root.left), heightBinary(root.right));
}

// Example
const root = new TreeNode('A',
  new TreeNode('B', new TreeNode('D'), null),
  new TreeNode('C')
);
console.log(heightBinary(root)); // 2

Recursive DFS (general N-ary tree, JS)

javascript

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

function heightN(root) {
  if (!root) return -1;
  let maxChild = -1;
  for (const c of root.children) {
    maxChild = Math.max(maxChild, heightN(c));
  }
  return maxChild + 1;
}

// Example
const tree = new NNode('A', [
  new NNode('B', [new NNode('D')]),
  new NNode('C')
]);
console.log(heightN(tree)); // 2

Iterative BFS by levels (binary tree, JS)

javascript

function heightBFS(root) {
  if (!root) return -1;
  let h = -1;
  const queue = [root];
  for (let i = 0; i < queue.length; ) {
    const levelSize = queue.length - i;
    for (let k = 0; k < levelSize; k++) {
      const node = queue[i++];
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    h++;
  }
  return h;
}

// For an N-ary tree add: if (node.children) for (const c of node.children) queue.push(c);

Complexity: time O(n) for any correct traversal (each node is visited once). Memory: O(h) for a recursive DFS (stack depth), O(w) for BFS (the maximum number of nodes at a level), where h is the height and w is the width of the tree.

Where it's used and why it matters

Self-balancing search trees (AVL, red-black): maintain O(log n) height for fast search/insert/delete.
Heaps: height ≈ ⌊log2 n⌋, giving O(log n) operations.
B-trees and their variants (database indexes): height O(log_t n), where t is the minimum degree.
Tries/prefix trees: height roughly equals the length of the longest key.

Common interview questions

How does height differ from depth? Height is the length of the longest downward path from a node; depth is the distance from the root to a node.
What's the height of an empty tree? It depends on the convention: -1 (in edges) or 0 (in nodes). Clarify it and stick to one.
What's the height of a single-node tree? 0 in edges, 1 in nodes.
How do you compute height quickly? Any traversal (DFS or BFS) in O(n), where n is the number of nodes.
How are height and balance related? The smaller the height for a fixed n, the more "balanced" the tree is; the ideal goal is O(log n).

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.