Suggest an edit

Improve this article

Refine the answer for “What is the height of a tree?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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.

### Related terms, so you don't mix them up

- 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).

Markdown · drag & drop images · ⌘B / ⌘I shortcuts853 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.