---
title: "Short note: Trees and applications"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:trees-and-applications-short-note"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/trees-and-applications-short-note
site: BCT Engineering
---

# Short note: Trees and applications

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2074 Bhadra, 4 marks; 2072 Asoj, 3 marks (asked 2 times)
- Video: [[Discrete Mathematics] Trees](https://www.youtube.com/watch?v=zEQZpTizgLo) — TrevTutor
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/trees-and-applications-short-note
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Write a short note on trees and their applications.

## Short answer

A tree is a connected undirected graph with no cycles; it has n–1 edges and at least two vertices of degree 1. Trees are used in binary search trees, expression trees, decision trees, Huffman coding, file systems, and network spanning trees.

## Answer

A **tree** is a connected undirected graph with no cycles (simple circuits).

**Properties** (n vertices):
- Exactly one simple path joins any two vertices.
- It has n − 1 edges.
- Removing any edge disconnects it; adding any edge creates exactly one cycle.
- A tree with n ≥ 2 has at least two leaves (vertices of degree 1).

A **rooted tree** has one vertex chosen as the root; edges are directed away from it, giving parent, child, ancestor, descendant, leaf and internal vertex. A **binary tree** has at most 2 children per vertex. For a full m-ary tree with i internal vertices: n = mi + 1 and leaves l = (m − 1)i + 1.

```text
          A            root A, children B, C
         / \           B has children D, E; leaves: D, E, C
        B   C          n = 5, edges = 4
       / \
      D   E
```

**Applications:**
- Binary search trees for fast searching and sorting.
- Expression trees in compilers and parse trees for syntax.
- Decision trees for classification and analysis of comparison sorts.
- Huffman coding trees for data compression.
- File system directories, organization charts and family trees.
- Spanning trees and minimum spanning trees for networks.
- Game trees and backtracking.

## Check yourself

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

1. A tree is:
   A. Any graph with no edges
   B. A graph with exactly one cycle
   C. A connected undirected graph with no cycles
   D. A directed cycle
   Answer: C. Connected and acyclic. (Key point: Definition)

2. A tree with n vertices has how many edges?
   A. n
   B. n + 1
   C. 2n
   D. n - 1
   Answer: D. This is a basic tree property. (Key point: Edges)

3. In a tree, how many simple paths join any two vertices?
   A. Exactly one
   B. At least two
   C. None
   D. Depends on the root
   Answer: A. Two paths would form a cycle. (Key point: Paths)

4. For a full m-ary tree with i internal vertices, the number of leaves is:
   A. mi + 1
   B. (m - 1)i + 1
   C. (m + 1)i
   D. mi - 1
   Answer: B. With n = mi + 1 vertices, leaves = n - i = (m - 1)i + 1. (Key point: Full m-ary)

## Related in Discrete Structure

- [Define tree; properties and applications](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Atree-definition-properties-applications) — Discrete Structure, chapter 4