Here is a complete, clear, and exam-oriented explanation of Trees — perfect for BCA/MCA/Engineering/Discrete Mathematics, Data Structures, and Graph Theory.

⭐ TREES – DETAILED DISCUSSION

A Tree is one of the most important structures in mathematics and computer science.
It appears in:

✔ Data structures (binary trees, AVL, B-trees)
✔ File systems
✔ AI search trees
✔ Compilers (syntax trees)
✔ Networks
✔ Graph theory

A tree is a connected acyclic graph.

⭐ 1. What is a Tree? (Formal Definitions)

A tree is a graph ( T = (V, E) ) with the following equivalent properties:

✔ Definition 1: Connected + Acyclic

A tree is a connected graph with no cycles.

✔ Definition 2: Unique Path Property

There is exactly one simple path between every pair of vertices.

✔ Definition 3: Minimal Connectivity

Removing any edge disconnects the tree.

✔ Definition 4: Edge Count Formula

A tree with ( n ) vertices has exactly:

[
|E| = n – 1
]

All these statements are equivalent.

⭐ 2. Basic Properties of Trees

Let a tree have n vertices (n ≥ 1):

✔ Property 1: Number of edges is n − 1

[
|E| = n-1
]

✔ Property 2: No cycles

A tree is always acyclic.

✔ Property 3: Connected

All vertices are reachable.

✔ Property 4: Adding an edge creates exactly one cycle

Tree + 1 edge = cycle.

✔ Property 5: Removing an edge disconnects the tree

Tree – 1 edge = disconnected graph.

✔ Property 6: Every tree has at least two leaves

A leaf is a vertex of degree 1.

✔ Property 7: Trees are bipartite

No odd cycles → always bipartite.

⭐ 3. Types of Trees

A. Free Tree / Undirected Tree

Standard graph-theoretic tree (no direction).

B. Rooted Tree

One vertex is chosen as the root.

Properties:

Parent-child relationships defined
Has height, levels, depth

Used in: data structures, file systems, XML, AI.

C. Binary Tree

Each node has at most two children.

Special cases:

Full binary tree
Complete binary tree
Perfect binary tree
Balanced binary tree (AVL tree)
Heap tree

D. Spanning Tree

A subgraph of a connected graph that:

includes all vertices
is acyclic
has exactly n – 1 edges

Used in network design and routing.

✔ Minimum Spanning Tree (MST)

Algorithms:

Kruskal
Prim

E. Directed Trees

Also called arborescences.

Directed edges away from (or towards) the root.

⭐ 4. Tree Terminology

✔ Root

Top of a rooted tree.

✔ Parent

Node from which edge leads to child.

✔ Child

Node reached from parent.

✔ Siblings

Nodes with same parent.

✔ Leaf / Terminal node

Node with no children.

✔ Internal node

Node with at least one child.

✔ Level of a node

Distance from root (starting at level 0 or 1).

✔ Height of a tree

Maximum level or depth.

✔ Subtree

Tree formed by a node and all its descendants.

⭐ 5. Important Theorems

⭐ Theorem 1: A tree with n vertices has n − 1 edges.

Proof idea:
By induction or using cycle-free + connected properties.

⭐ Theorem 2: Adding an edge to a tree creates exactly one cycle.

Reason:
A tree has a unique path between any two vertices.
Adding an edge between them creates an alternate path → cycle.

⭐ Theorem 3: Removing any edge disconnects the tree.

Because every edge is a bridge (critical connection).

⭐ Theorem 4: Every tree has at least two leaves.

Used in network routing and coding theory.

⭐ 6. Applications of Trees (Very Important)

✔ Computer Science

File systems (NTFS/FAT)
Binary search trees (BST)
AVL trees
B-trees, B+ trees (DBMS)
Heaps
Tries (prefix trees)
Parse trees in compilers
AI search trees (DFS, BFS)
Game trees (minimax)
Huffman coding (compression)

✔ Networking

Routing protocols
Spanning tree protocol (STP)
Connected acyclic sub-networks

✔ Mathematics & Graph Theory

Representation of hierarchies
Phylogenetic trees
Decision trees
Lemmas and decomposition theorems

✔ Electrical Engineering

Circuit design
Signal flow trees

✔ Operations Research

Project scheduling
Organization charts

⭐ 7. Difference Between Trees and General Graphs

Feature	Tree	General Graph
Cycles	None	May have
Connectivity	Always connected	May be disconnected
Edges	n – 1	Up to n(n−1)/2
Paths	Unique path between any pair	Multiple possible
All vertices reachable?	Yes	Not necessary
Use	Hierarchies, search, structure	Complex networks

⭐ 8. Relation Between Trees and Hamiltonian/Eulerian Paths

A tree always has a Hamiltonian path (simple traversal).
A tree never has a Hamiltonian cycle (no cycles).
A tree never has Eulerian cycle.
A tree has Eulerian trail only if it has exactly two vertices with odd degree.

⭐ 9. How to Identify a Tree

A graph is a tree if:

✔ It is connected AND has n–1 edges

✔ It is acyclic AND has n–1 edges

✔ It is acyclic AND connected

✔ It has a unique path between every pair of vertices

Any one of these is sufficient.

⭐ 10. Exam-Oriented Definitions to Remember

Tree

A connected acyclic graph.

Rooted Tree

Tree with a distinguished root node.

Spanning Tree

A subgraph that includes all vertices and is a tree.

Binary Tree

Every node has ≤ 2 children.

Leaf

Vertex of degree 1.

Height of Tree

Length of longest path from root to leaf.

⭐ Quick Summary Sheet

✔ Tree = connected + acyclic
✔ Edges = n − 1
✔ Unique path between any two vertices
✔ Removing an edge disconnects
✔ Adding an edge creates cycle
✔ At least two leaves
✔ Trees are bipartite
✔ Used in data structures, AI, networks, compilers, DBMS