---
title: "Level, height, m-ary and balanced tree"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:tree-level-height-m-ary-balanced"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/tree-level-height-m-ary-balanced
site: BCT Engineering
---

# Level, height, m-ary and balanced tree

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2070 Bhadra, 2+2 marks
- Video: [Video_44:  m-ary Tree Definition](https://www.youtube.com/watch?v=92CCEGjcnSY) — Ajeesh Ramanujan
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/tree-level-height-m-ary-balanced
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Define level and height of tree. What is full m-ary tree and balanced tree?

## Short answer

Level of a vertex is its distance from the root; height is the maximum level. A full m-ary tree has every internal vertex with exactly m children. A balanced tree has all leaves on the last or second-last level.

## Answer

#### Level and height
In a rooted tree, the **level** of a vertex is the length of the unique path from the root to it. The root is at level 0, its children at level 1, and so on. The **height** of the tree is the maximum level of any vertex (the length of the longest path from the root).

```text
   r            level 0
  / \
 a   b          level 1
/ \    \
c  d    e       level 2    -> height = 2
```

#### Full m-ary tree
A rooted tree is an **m-ary tree** if every internal vertex has at most m children. It is a **full m-ary tree** if every internal vertex has **exactly m** children. For m = 2 it is a full binary tree.

If a full m-ary tree has i internal vertices, then it has n = mi + 1 vertices and l = (m − 1)i + 1 leaves. Example: a full binary tree with 3 internal vertices has 2·3 + 1 = 7 vertices and 4 leaves.

#### Balanced tree
An m-ary tree of height h is **balanced** if all its leaves are at level h or h − 1. For example, a binary tree with root r, children a and b, and two children c, d under a has leaves b (level 1) and c, d (level 2), with h = 2, so it is balanced. A tree with one leaf at level 1 and another at level 3 is not balanced.

An m-ary tree of height h has at most m^h leaves.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. In a rooted tree, what is the height?
   A. The number of vertices
   B. The number of leaves
   C. The level of the root
   D. The maximum level of any vertex
   Answer: D. Level = path length from root; height is the largest level (longest path). (Key point: Level and height)

2. What distinguishes a full m-ary tree from an m-ary tree?
   A. Every internal vertex has exactly m children, not at most m
   B. All leaves are on one level
   C. The root has m children only
   D. It has height m
   Answer: A. An m-ary tree allows at most m children; full requires exactly m. (Key point: Full m-ary)

3. A full binary tree has 3 internal vertices. How many vertices and leaves?
   A. 6 vertices, 3 leaves
   B. 7 vertices, 4 leaves
   C. 8 vertices, 5 leaves
   D. 7 vertices, 3 leaves
   Answer: B. n = 2*3 + 1 = 7 and leaves = (2 - 1)*3 + 1 = 4. (Key point: Full binary count)

4. When is an m-ary tree of height h balanced?
   A. When every internal vertex has m children
   B. When all leaves are at level h or h - 1
   C. When it has exactly m^h leaves
   D. When the root has equal subtrees
   Answer: B. A leaf at level 1 together with one at level 3 breaks the condition. (Key point: Balanced)

## Related in other subjects

- [Correlation: tree circumference and height](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Atrees-circumference-height-correlation) — Probability and Statistics, chapter 5
- [AVL tree for 10 20 30 50 45 40 8 5 3](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-10-20-30) — Data Structure and Algorithm, chapter 6
- [AVL tree for 10, 20, 30, 35, 50, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-10-20-30-35) — Data Structure and Algorithm, chapter 6
- [T/F: tower height same for single/double circuit](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Atf-tower-height-single-double-circuit) — Transmission and Distribution System Design, chapter 4