About Trees

Tree is a discrete structure that represents hierarchical relationships between individual elements or nodes. A tree in which a parent has no more than two children is called a binary tree.

Tree and its Properties

Definition − A Tree is a connected acyclic undirected graph. There is a unique path between every pair of vertices in G

. A tree with N number of vertices contains (N−1)

number of edges. The vertex which is of 0 degree is called root of the tree. The vertex which is of 1 degree is called leaf node of the tree and the degree of an internal node is at least 2.

Example − The following is an example of a tree −

Centers and Bi-Centers of a Tree

The center of a tree is a vertex with minimal eccentricity. The eccentricity of a vertex X

in a tree G is the maximum distance between the vertex X

and any other vertex of the tree. The maximum eccentricity is the tree diameter. If a tree has only one center, it is called Central Tree and if a tree has only more than one centers, it is called Bi-central Tree. Every tree is either central or bi-central.

Algorithm to find centers and bi-centers of a tree

Step 1 − Remove all the vertices of degree 1 from the given tree and also remove their incident edges.

Step 2 − Repeat step 1 until either a single vertex or two vertices joined by an edge is left. If a single vertex is left then it is the center of the tree and if two vertices joined by an edge is left then it is the bi-center of the tree.

Problem 1

Find out the center/bi-center of the following tree −

Solution

At first, we will remove all vertices of degree 1 and also remove their incident edges and get the following tree −

Again, we will remove all vertices of degree 1 and also remove their incident edges and get the following tree −

Finally we got a single vertex ‘c’ and we stop the algorithm. As there is single vertex, this tree has one center ‘c’ and the tree is a central tree.

Problem 2

Find out the center/bi-center of the following tree −

Solution

At first, we will remove all vertices of degree 1 and also remove their incident edges and get the following tree −

Again, we will remove all vertices of degree 1 and also remove their incident edges and get the following tree −

Finally, we got two vertices ‘c’ and ‘d’ left, hence we stop the algorithm. As two vertices joined by an edge is left, this tree has bi-center ‘cd’ and the tree is bi-central.

Labeled Trees

Definition − A labeled tree is a tree the vertices of which are assigned unique numbers from 1 to n. We can count such trees for small values of n by hand so as to conjecture a general formula. The number of labeled trees of n number of vertices is nn−2

. Two labeled trees are isomorphic if their graphs are isomorphic and the corresponding points of the two trees have the same labels.

Example

Unlabeled Trees

Definition − An unlabeled tree is a tree the vertices of which are not assigned any numbers. The number of labeled trees of n number of vertices is (2n)!(n+1)!n!

(n^th Catalan number)

Example

Rooted Tree

A rooted tree G

is a connected acyclic graph with a special node that is called the root of the tree and every edge directly or indirectly originates from the root. An ordered rooted tree is a rooted tree where the children of each internal vertex are ordered. If every internal vertex of a rooted tree has not more than m children, it is called an m-ary tree. If every internal vertex of a rooted tree has exactly m children, it is called a full m-ary tree. If m=2

, the rooted tree is called a binary tree.

Binary Search Tree

Binary Search tree is a binary tree which satisfies the following property −

• X

in left sub-tree of vertex V,Value(X)≤Value(V)

·  ·  Y in right sub-tree of vertex V,Value(Y)≥Value(V)

•  

So, the value of all the vertices of the left sub-tree of an internal node V

are less than or equal to V and the value of all the vertices of the right sub-tree of the internal node V are greater than or equal to V

. The number of links from the root node to the deepest node is the height of the Binary Search Tree.

Example

Algorithm to search for a key in BST

A spanning tree of a connected undirected graph G is a tree that minimally includes all of the vertices of G

. A graph may have many spanning trees.

Example

Minimum Spanning Tree

A spanning tree with assigned weight less than or equal to the weight of every possible spanning tree of a weighted, connected and undirected graph G

, it is called minimum spanning tree (MST). The weight of a spanning tree is the sum of all the weights assigned to each edge of the spanning tree.

Example

Kruskal's Algorithm

Kruskal's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted graph. It finds a tree of that graph which includes every vertex and the total weight of all the edges in the tree is less than or equal to every possible spanning tree.

Algorithm

Step 1 − Arrange all the edges of the given graph G(V,E)

in non-decreasing order as per their edge weight.

Step 2 − Choose the smallest weighted edge from the graph and check if it forms a cycle with the spanning tree formed so far.

Step 3 − If there is no cycle, include this edge to the spanning tree else discard it.

Step 4 − Repeat Step 2 and Step 3 until (V−1)

number of edges are left in the spanning tree.

Problem

Suppose we want to find minimum spanning tree for the following graph G using Kruskal’s algorithm.

Solution

From the above graph we construct the following table −

Edge No.	Vertex Pair	Edge Weight
E1	(a, b)	20
E2	(a, c)	9
E3	(a, d)	13
E4	(b, c)	1
E5	(b, e)	4
E6	(b, f)	5
E7	(c, d)	2
E8	(d, e)	3
E9	(d, f)	14

Now we will rearrange the table in ascending order with respect to Edge weight −

Edge No.	Vertex Pair	Edge Weight
E4	(b, c)	1
E7	(c, d)	2
E8	(d, e)	3
E5	(b, e)	4
E6	(b, f)	5
E2	(a, c)	9
E3	(a, d)	13
E9	(d, f)	14
E1	(a, b)	20

Since we got all the 5 edges in the last figure, we stop the algorithm and this is the minimal spanning tree and its total weight is (1+2+3+5+9)=20

.

Prim's Algorithm

Prim's algorithm, discovered in 1930 by mathematicians, Vojtech Jarnik and Robert C. Prim, is a greedy algorithm that finds a minimum spanning tree for a connected weighted graph. It finds a tree of that graph which includes every vertex and the total weight of all the edges in the tree is less than or equal to every possible spanning tree. Prim’s algorithm is faster on dense graphs.

Algorithm

• Initialize the minimal spanning tree with a single vertex, randomly chosen from the graph.
• Repeat steps 3 and 4 until all the vertices are included in the tree.
• Select an edge that connects the tree with a vertex not yet in the tree, so that the weight of the edge is minimal and inclusion of the edge does not form a cycle.
• Add the selected edge and the vertex that it connects to the tree.

Problem

Suppose we want to find minimum spanning tree for the following graph G using Prim’s algorithm.

Solution

Here we start with the vertex ‘a’ and proceed.

This is the minimal spanning tree and its total weight is (1+2+3+5+9)=20

.