Tree
A tree is a special type of graph that is:
Connected (there is a path between any two vertices),
Acyclic (contains no cycles).
Formally,
A tree is a connected undirected graph with no cycles.
Properties of Trees
Let a tree have n vertices and e edges:
1. A tree with n vertices has exactly n - 1 edges.
2. There is exactly one path between any two vertices in a tree.
3. Adding any edge to a tree will create a cycle.
4. Removing any edge from a tree will disconnect the graph.
5. A tree with n ≥ 1 always has at least one leaf (a vertex of degree 1).
6. A tree is minimally connected, i.e., if any edge is removed, it becomes disconnected.
7. A tree is maximally acyclic, i.e., if any edge is added, it forms a cycle.
Mathematical Formulations
If G is a tree with n vertices:
|E| = |V| - 1
G is connected
G has no cycles
Examples of Trees
Example 1: Simple Tree
A
/\
B C
/\
D E
Vertices: A, B, C, D, E → n = 5
Edges: (A, B), (A, C), (B, D), (B, E) → e = 4
e = n - 1 → Tree confirmed.
Example 2: Binary Tree (used in computer science)
10
/ \
20 30
/ \
40 50
This is a binary tree: each node has at most two children.
Also satisfies tree properties: connected, no cycles, n = 5, e = 4.
Applications of Trees
File system hierarchy
Binary Search Trees (BSTs)
Expression Trees
Network Routing (Spanning Trees)
Decision Trees in AI
Rooted Tree
🔹 Definition:
A rooted tree is a tree in which one vertex is designated as the root, and every edge directs
away from it, defining a clear parent-child hierarchy.
Formally:
A rooted tree is a tree (acyclic connected graph) with one special vertex called the root, from
which every other vertex is reachable via a unique path.
In a rooted tree, one node is designated as the root. This structure creates a hierarchy where
every other node is connected either directly or indirectly to the root, forming levels of
relationships.
🔹 Key terminology :
1. Root:
o The topmost node in the tree.
o Has no parent.
2. Parent-Child Relationship:
o If two vertices are connected, one is the parent (closer to the root) and the other is
the child (further from the root).
o Example: In edge A → B, A is the parent of B.
3. Siblings:
o Nodes that share the same parent.
o Example: If B and C are both children of A, then B and C are siblings.
4. Ancestors:
o All nodes along the path from a node to the root (excluding the node itself).
o Example: For node E, if the path is E → B → A, then ancestors of E are B and A.
5. Descendants:
o All nodes that are reachable downward from a node.
o Includes children, grandchildren, etc.
o Example: For node A, descendants could be B, C, D, E, F if it’s the root.
6. Leaf Node:
o A node with no children.
o Example: In a family tree, these are the youngest generation.
7. Subtree:
o Any node with its descendants forms a subtree.
o Useful in recursion and algorithms.
🖼️Example Tree:
A
/\
B C
/\ \
D E F
In this tree:
A is the root.
B and C are children of A.
D and E are siblings (children of B).
A is an ancestor of D, E, and F.
D, E, and F are leaf nodes.
Subtree rooted at B includes B, D, and E.
Trees and Sorting
Trees, especially binary trees, are widely used to implement efficient sorting algorithms.
Here’s how the two are related:
🔹 1. Binary Search Tree (BST) and Sorting
A Binary Search Tree is a rooted binary tree where:
The left subtree contains only nodes less than the parent node.
The right subtree contains only nodes greater than the parent node.
No duplicate nodes.
If you insert elements into a BST and perform in-order traversal, you will get the elements in
sorted order.
Example:
Given unsorted array:
[7, 3, 9, 1, 5]
Insert into BST:
/\
3 9
/\
1 5
In-order traversal:
1→3→5→7→9
Insert into BST:
Given list:
[8, 4, 10, 2, 6, 9, 12]
Build BST:
8
/\
4 10
/\ /\
2 6 9 12
In-order traversal (Left → Root → Right):
2 → 4 → 6 → 8 → 9 → 10 → 12
Weighted Tree
🔹 Definition:
A weighted tree is a tree (connected acyclic graph) in which each edge has an associated
numerical value (weight).
Formally: A weighted tree is a connected, acyclic, undirected graph where weights (usually
positive integers or real numbers) are assigned to edges.
✅ Uses:
Representing distances, costs, or capacities.
Used in:
o Minimum Spanning Tree (MST) algorithms (like Kruskal’s, Prim’s)
o Routing, network design, optimal paths
Example:
A
/\
(3) (5)
B C
Edge A-B has weight 3
Edge A-C has weight 5
Tree is still acyclic and connected, but now has weights.
Cycle (in Graph Theory)
🔹 Definition:
A cycle is a path of edges and vertices in which:
The starting and ending vertex are the same,
And no edge is repeated.
In a tree, by definition, there are no cycles.
If a cycle is present, the graph is not a tree.
Example of Cycle (not a tree):
A
/\
B---C
A-B-C-A forms a cycle , not a tree.
Connectedness in Trees
🔹 Definition:
A graph is connected if there is a path between every pair of vertices.
A tree is always connected — this is one of its defining properties.
Removing any edge from a tree makes it disconnected.
A tree is a minimally connected graph (just enough edges to stay connected without
forming cycles).
If a graph is:
Connected and Acyclic → It is a Tree.
Connected and has n vertices → It must have n−1 edges to be a tree.
Relation Digraph (Directed Graph / Digraph)
🔹 Definition:
A relation digraph is a graphical representation of a binary relation using a directed graph.
Vertices represent elements of the set.
Directed edges (arcs) represent the relation between elements.
Example:
Let A = {1, 2, 3} and R = {(1,2), (2,3), (1,3)}
The digraph:
1→2→3
\_____↑
Arrow from 1 to 2 means (1,2) ∈ R
Arrow from 1 to 3 means (1,3) ∈ R
Transitive Closure of a Relation
🔹 Definition:
The transitive closure of a relation R is the smallest transitive relation that contains R.
If (a, b) ∈ R and (b, c) ∈ R, then to make R transitive, (a, c) must also be in R.
Notation:
If original relation is R, then its transitive closure is R⁺.
Example:
Let R = {(1,2), (2,3)}
To make it transitive, we add (1,3)
So, R⁺ = {(1,2), (2,3), (1,3)}
Warshall’s algorithm;
If there is a direct edge, write the weight.
If there is no edge, write ∞ (infinity).
Diagonal elements (distance from node to itself) are 0.
