---
title: "Define tree; properties and applications"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:tree-definition-properties-applications"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/tree-definition-properties-applications
site: BCT Engineering
---

# Define tree; properties and applications

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2069 Bhadra, 1+2+4 marks
- 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/tree-definition-properties-applications
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Define a tree and discuss its various properties as well as applications of trees.

## Short answer

A tree is a connected acyclic graph. Key properties: n vertices, n-1 edges, unique path between any two vertices, at least two leaves. Applications include binary search trees, decision trees, Huffman coding, network spanning trees, and hierarchical data structures.

## Answer

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

#### Properties
For a tree T with n vertices:
1. There is exactly one simple path between any two vertices.
2. T has exactly n − 1 edges.
3. Removing any edge disconnects T; adding any edge between two vertices creates exactly one cycle.
4. A tree with n ≥ 2 vertices has at least two leaves (vertices of degree 1).
5. A graph is a tree iff it is connected with n − 1 edges, or acyclic with n − 1 edges.
6. A **rooted** tree has a root, and the terms parent, child, sibling, ancestor, descendant, leaf and internal vertex are defined by direction away from the root. In a full m-ary tree with i internal vertices, n = mi + 1 and leaves l = (m − 1)i + 1.

```text
        r            n = 6 vertices, 5 edges
       / \           leaves: c, d, e
      a   b          internal: r, a, b
     / \   \
    c   d   e
```

#### Applications
- Binary search trees, heaps (searching, sorting, priority queues).
- Expression trees and parse trees in compilers.
- Decision trees (classification, lower bound for sorting).
- Huffman coding for data compression (prefix codes).
- Hierarchical structures: file systems, organization charts, XML/HTML DOM.
- Spanning trees for network design (minimum spanning tree) and routing.
- Game trees and backtracking search.

## Check yourself

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

1. Which defines a tree?
   A. A directed graph with a source and sink
   B. A connected undirected graph with no simple circuits
   C. Any graph with n edges
   D. A graph where each vertex has degree 2
   Answer: B. A tree is connected and acyclic. (Key point: Definition)

2. How many simple paths join any two vertices of a tree?
   A. At least two
   B. None in general
   C. Exactly one
   D. Exactly n - 1
   Answer: C. Two paths would create a cycle; connectivity guarantees at least one. (Key point: Paths)

3. For a tree with n >= 2 vertices, which is true?
   A. It has n edges and one leaf
   B. It has n - 1 edges and at least two leaves
   C. It has n + 1 edges and no leaves
   D. It has n - 1 edges and exactly one leaf
   Answer: B. Trees have n - 1 edges and at least two vertices of degree 1. (Key point: Edges and leaves)

4. A full m-ary tree has i internal vertices. How many leaves?
   A. (m - 1)i + 1
   B. mi + 1
   C. mi
   D. (m + 1)i - 1
   Answer: A. n = mi + 1 and leaves = n - i = (m - 1)i + 1. (Key point: Full m-ary formula)

## Related in Discrete Structure

- [Short note: Trees and applications](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Atrees-and-applications-short-note) — Discrete Structure, chapter 4, asked 2×
- [Short note: Spanning tree and applications](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aspanning-tree-and-applications) — Discrete Structure, chapter 4
- [Short note: Spanning tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aspanning-tree-short-note) — Discrete Structure, chapter 4, asked 3×

## Related in other subjects

- [B-tree properties; order 5 for 3, 14, 7, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-properties-order5-3-14) — Data Structure and Algorithm, chapter 6, asked 2×
- [Spanning tree properties; Round Robin MST](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aspanning-tree-properties-round-robin) — Data Structure and Algorithm, chapter 10
- [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
- [Huffman tree definition and example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ahuffman-tree-properties) — Data Structure and Algorithm, chapter 6