2

TREES
A connected graph that contains no crrcmt
· · · 11
1s ca ed a tree. Trees were used as long ago as 1857,
,hen the English mathematician Arthur Cayley used them to count certain types of chemical compounds.
1ince that time, trees have been employed to solve problems in a wide verity of disciplines.

Trees are particularly useful in computer science Trees are employed to construct efficient algorithms
for locating items in a list. They are used to construct networks with the least expensive set of telephone
lines linking distributed computers. Trees can be used to construct efficient codes for storing and
transmitting data. Trees can model procedures that are carried out using a sequence of decisions. This
makes trees valuable in study of Computer Science.

Definition Tree : A graph G is called a tree if

(i) G is connected

(ii) G has no cycles.

Following graphs are trees : ~

~ /n X
Graph
b

a
f::J C

d
is not tree as it contains a cycle b, c, d, b

...._ / . s i't contains a disconnected component a b.

~ 1s not tree a
Similarly ..
a·- ~-1
· .. . fi ll that a tree has to be a simple graph i.e. having neither a self
above definition, it o ows
Re mar}{ : From b se both of them from cycle.
arallel edges ecau .. . . . .
loop nor P . d 'f ery edge of tree is assigned a direction, otherwise tree 1s undirected.
. .d to be directe 1 ev
Note: Tree is sat
551
 TERMINOLOGY USED IN TREE
When we discuss tree, we encounter a number of terms that are necessary to underS t a nd ·
The tenns used are :
a

d
e
• NODE OR VERTEX: Node is key component of tree which stores information and can have on
more links for connecting to other nodes.
• EDGE or LINK: A directed line from one node to other node is called edge, link, arc or branch fl
tree. ln above figure ab, ac etc are links.
• ROOT: The vertex having indegree zero is called root of tree. In above tree root of tree is a.
• PA TH : A Path is a sequence of nodes when we traverse from one node to other along the e
which connect them e.g. path from a to f is a, c, f
• LEVEL: Level of node is an integer value that measures the distance of a node from the root. Ro
at level 0. The child(s) of root are at level 1 and so on.
• HEIGHT: Height of node is the length of longest path from node to a leaf. All the leaves are
height 0. Height of root is height of tree. In above tree, height of d, e, f is 0, Height of b, c is 1
height of a is 2.
• DEPTH: The depth of node is the length of path from node to root of tree Root has depth 0.
In above tree depth of a is O depth of b, c is 1. Depth of d, e,f is 2.
• ROOTED TREE : A rooted tree is a directed tr.e.e. _which contains a unique vertex 'r' such that ·
degree of r is zero and every other vertex has in-degree one. The vertex 'r' is called root of root
tree.
For example:

4.,d ) f)
Jv b
C)
a

:L •-
c
j;,I
~ d .,_, 'e Y',i J
is a rooted tree with root 'a'.
• PARENT A~~U OFFSPRING : Jf (x, y) is any directed edge then x is called parent of y and y i
called offspnng of x. Root of tree has no parent whereas every other node has a unique paren
A parent can have several offsprings. Offspring is also called mild or son.,
In above tree a is parent of b and c. b has two offsprings d and e.

,.,,. • LEAF : A node having no offsprings (outdegree = 0) is called'a leaf. In fig. d, e, /are leaves. Leaf i
I
,·.
al so called ~xternal or terminal node.

• SIBLINGS : Two nodes having same parent are called sl~- ln figure b, care siblings of a .

• INTERIOR NODE : Node having at least one child is can Interior node .
h C ~-....,...,L·'••' ,Y~,>).., ~
 ANCESTOR ·• Ance stors of a 553
vertex, excluding th Vertex other th
e Vertex itself and in d. an root are the vertices in the path from root to this
1
DESCENDANT : Desc d c u mg th e root. For example, ancestors of dare band a.
• en ants of a vertex 'V'
For example : Descendant f are those vertices that have 'V' as an ancestor.
s O b are d and e
SUBTREE . If ' ' . . / [Link] i i ( I • /
• . . . a is any vertex in a tr h . . . .
consistmg of a and its descend t ee, t e subtree with a as its root 1s the subgraph of tree
. ti an s &re all edges incident to these descendants. ·
In given ig. subtree of bis T(b) h
- . as s own : w lv.l\..1_ 6 V\ ) k r
Le ?-- \
L b

•
d/\ . e

FOREST: A forest is an undirected graph whose components are all trees .

• BINARY TREE :
Let T is a tree. We say T is n-tree or n-an: tree if every vertex_I1a$ at~ost n .Qffspring~. In particular, if
n = 2 then tree is called binary tree. So binary tree is that tree in which every node can have 0, I or 2
offsprings.
• COMPLETE BINARY TREE :
In n-tree, if every vertex of T, other than leaves, has exactly n-offsprings then we say T is complete n-
Tree. For n = 2 we say tree ~s co~inary tree.

Example(i) bJ"'-.r is a Binary Tree .

./).f\
. le b is left child of a and c is right child of a.
In this examp , .
ex (except leaves) has 2 children so tree is complete Bmary Tree.
Moreover every vert
is a 3-ary tree. But is not complete.
(il)

p operties of Tree
2.1. r th between every pair of vertices in a tree T.
h re is one and only one pa . .
Property 1. T e Th fi re there exists atleast one path between every pa1r of vertices
. T is a connected graph. ere o
Proof: S mce
in tree T · rt' v and v 2 there exists two distinct paths. The union of these two
b tween two ve ices 1 •
suppose that e_ . d then T cannot be a tree. Thus there is one and only path between every parr
·11 contain a ctrcUJt an
paths W 1
·ces in a tree T.
ofvert1
.. • uperty 2. If in a graph G, there is one and only one path between every pair of vertices, then G is tree.
Proof: Since there is one and only one path between every pair of vertices in G implies that G is connee1e4
graph. Suppose that G contain a circuit, then there is atleast one pair of vertices V1, v, (say) _such that there
are two distinct path between them. A contradiction to the given fact and so G cannot have crrcu1t. Hence G
is a connect graph without circuit implies that G is a tree.
Property 3. A tree with n vertices has n I edges.

Proof. We shall prove the result by induction on the number of vertices n.

Obviously the result is true for n =- 1, 2, 3 as
When n = I we have • Zero edge
When n = 2 we have
I One edge

Whenn=3 we have
vI Two edge.

Let us assume that the result is true for all tree with less than n vertices.
Consider a tree T with n vertices. Let ek be an edge with end verities V; and v . Since there is one and
1
only one path between every pair of vertices i.e., there is no other path between V; and v except e,.
Therefore deletion of edge from Twill disconnect the graph as shown below. 1

Therefore T- e, consist of exactly two component T I and T2 (say). Since there is no circuits in T each
of these components is a tree. Further, both of these tree T 1 and T 2 have less then n--vertices, therefore by
supposition, each tree will contain edge one less then the number of vertices in it. So T- e, consist of (n - 2)
edges implies that T has exactly (n - 2) + 1 = n - l edges. This completes the induction.
Note : It may be noted that the vertices of a tree are connected together with the minimum number of
edges.

Definition. Minimally connected graph_:

A connected graph G is said to be minimally connected if removal of any edge from it disconnect
the graph.
For Example :

are minimally connected graphs.

IC
I .JtJ , { }

) f\ )
Y1 r
 r~s
·r. . . . --------------------~
,,,,,,-:;:-~;:;:::::::-::~:-:-
property 4. A graph is a tree if and only 555
I it is m101mall
proof: Firstly, let the graph T be t Yconnected.
a ree. Therefore T m t b
nuniJna11Y connecte d . Then there must 1st. us e a connected graph. If possible let T be not
ome circuit which implies that T 1·s tex s an edge e, in T such that T - e1 is connected. Th;refore e, is in
S no a tree aco t ct· .
versely. Let T be a . . ' n ra tct10n. Hence T must be minimally connected.
Con mm1mally connected h
remove one of the edge in the circuit and still lgrap · Therefore T cannot have a c~cuit otherwise we could
eave the graph connected. Hence T ts a tree.
. . .
Property 5. A graph G with n vertices anct (n - l) edges and no ctrcmt 1s connected.
Proof : Let there exist a graph G with ·
will consists of two or more cir . _n vertices, (n-1) ed~es and no circuit whic~ is disconnected. Then G
cmt less component. Without loss of generality, let G consist of two
components G I and G2 as shown below :
G1
e

v1

Now, add an edge e between the vertices Vi in G 1 and v 2 and G2 • Since there is no path between vi and v 2
in G so by adding an edge e did not create a circuit in G. Thus G U e is a circuit less connected graph.
l5 onn:.:
i.e., G U e is a tree in other words, a tree has n vertices an n edges, which is not possible. Hence a graph
xcep:: with n vertices and (n - 1) edges and no circuit is connected.
Remark : Five different but equivalent definition of tree are A graph G with n vertices is called a tree if
( z) G is connected and has no circuit.
(iz) G is connected and has (n - 1) edges.
(iii) G has n - 1 edges and no circuit.
(iv) there is exactly one path between every pair of vertices in G.
(v) G is minimally connected.
2.2. In any non-trivial tree, there are atleast two(p~ndent vertices; u.'?.a:~~o,11, o. UJ./'. -tv..ro 1-t"'-
Or ~"' cl.:,.. ,,J l~

· · 1tree , there are at least two vertices of degree 1.

In any non-t nvia
-trivial tree with n vertices, then T has n-1 edges.
Proof: Let T b e anOn
By fundamental theorem on graph theory

tj:=c]
deg (v,) = 2 (n - 1) = 2n-2
... (1)

'b) let T contain only one vertex (say) vi of degree 1. Then

IfpoSSI e, .
deg (vi) - 1 and deg (v,) ~ 2 for t - 2, 3, 4, .... , n

t
i= 1
deg(v,) = deg (vi) -I
n
Ldeg ('v,)
i 2
n
=I+ Ldeg(v 1) ~ 1 +-2 (n I) 2n- l ... (2)
,---2

I
✓
 From (1) and (2), we get 2 n - 2 2: 2 n - 1, a contra diction .
T must have more than one vertex of degree I i.e., T has atleast two vertices of degree
J.
Example 1: Which of follow ing graphs are trees?

(a)
(b) V11 (c)

(d) (e) (f)

Sol. (a) Numb er of vertice s = 6

Numb er of edges = 5 as edges = n-1 and graph has no cycle so it repres ent
a tree.
(b) Since graph contains t~o disconnected compo nents so it is not a tree.
( c) Numb er of vertices = 6
Numb er of edges = 5 as edges = n-1 and graph has no cycle so it repres ent
a tree.
( d) Graph contains a cycle so it is not a tree.
( e) Graph is a tree ·.· it contains no cycle and numbe r of edges (6) = numbe r of
vertices (7)- 1.
if) Graph is not tree as it contains a cycle.
Example 2. Let A= {a, b, c, d, e} R = {(a, d), (b, c), (c, a), (d, e)} check whether Risa
tree. If it is, find
the root.
Sol. We are given five vertices and four edges. R will from tree iff
(i) edges connec t all vertices
. (ii) edges will not form cycle among vertices.
From R, it is clear 'b' has indegree O.'IfR is tree then b must be root. So taking
bas root we construct
all edges as below

As no eye le ]·s 1s:-.•0 rmed , so Risa tree and bis root of tree.
ve that A = {1, 2, 3, 4, 5, 6} R = {(I, I), (2, 1), (2, 3), (3, 4), (4, 5), (4, 6)} is not
Example 3 . P ro a tree.
rt' ces - 6 and number of edges = 6. So R cannot be a tree.
Sol. As numbe r o f ve t •
. f edges = n-1, n == no. of vertices.
m tree no. o
fJEES.----~~~-------
y' "d h ------------------~5~5 7
ple 4. Const er t e tree.
£Ill 111 a
(a) Ust all leve\-3 vertices.
(b) List al\ leaves.
(c) What are siblings of d?
I
(d) Draw the Tree T(b).
(e) What is level and height of m ?
Sol. (a) Root of tree is a. So level of a= o
At \eve\ one we have b, c, d
at level two we have e, h, i, j, k, l at level three we have f, g and m.
(b) Leaves are vertices that have no offsprings. In given tree leaves aref, g, h, i,j, n and/.
(c) Siblings of dare band c b, c, d have same parent a.
( d') Tree T(b) is as shown

(e) Level of m = 3
Height of m = 3 + l = 4 (Height = level + 1)