Introduction to Trees - Discrete Mathematics

What is a Tree in Discrete Mathematics?

The hierarchical relationships between the individual elements or nodes are represented by a discrete structure called as Tree in Discrete Mathematics. A Tree is said to be a binary tree, which has not more than two children.

Tree and its Properties

Definition – An acyclic undirected graph that is connected is known as a Tree. For a tree with N number of vertices, the number of edges is (N−1). The root of the tree is the vertex with 0 degree. The vertex with degree 1 is the leaf node and the degree of the internal node is at least 2.

Example − The following is an example of a tree −

Tree

What are the Centers and Bi-Centers of a Tree?

The vertex with minimal eccentricity is known as the center of a tree. The maximum distance between the vertex X and any other vertex of the tree is known as the eccentricity of the vertex X in tree G. The tree diameter is the minimum eccentricity.

The tree with one center is Central Tree and the tree with more than one centers is called as Bi-central Trees. Every tree is either central or bi-central.

Algorithm to find centers and bi-centers of a tree

Step 1 – From a given tree, all the vertices of degree 1 are removed along with the incident edges.

Step 2 – Step 1 is repeated till a single vertex or two vertices are joined by the left out edge. If single vertex is left, it is the center of the tree and if two vertices joined by the edge is left, it is the bi-center of the tree.

Problem 1

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

Tree 1

Solution

All the vertices of degree 1 are removed along with the incident edges for getting the following tree:

Tree Solution

Repeat the same step, remove all the vertices of degree 1 along with the incident edges and the following tree is obtained:

Solution Removing Vertex

Once the single vertex ‘c’ is obtained, the algorithm is stopped. The tree is a central tree as there is single vertex with one center ‘c’.

Problem 2

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

Tree 2

Solution

All the vertices of degree 1 are removed along with the incident edges for getting the following tree:

Tree 2 Solution

Repeat the same step, remove all the vertices of degree 1 along with the incident edges and the following tree is obtained:

Solution removing vertex

It is left with two vertices ‘c’ and‘d’ and hence the algorithm is stopped. The tree is bi-central as two vertices joined by an edge is left.

What are Labeled Trees?

The tree for which unique numbers from 1 to n are assigned to its vertices is known as a labelled tree. Given the smaller values of n, such trees are countable by hand for deriving a general formula. If the graphs of the trees are isomorphic, the two labelled trees are also isomorphic and same labels are carried by the corresponding points of the two trees.

Example

Labelled Tree with 2 vertex

Labelled Tree with 3 vertex

What are Unlabeled Trees?

The Trees for which the vertices are not assigned any numbers is an unlabelled tree. For n number of vertices, the number of unlabelled trees is

Example

Unlabelled Tree with 2 vertex

Unlabelled Tree with 3 vertex

Unlabelled Tree with 4 vertex

What is a Rooted Tree?

When a acyclic graph is connected with a special node called root of the tree, the tree is said to be a rooted tree where every edge either directly or indirectly originates from the root. The children of each internal vertex of an rooted tree are ordered, then it is an ordered rooted tree. If the children of each internal vertex of the rooted tree are more than m, it is known as m-ary tree. If there are m children for every internal vertex of the rooted tree, it is known as full m-ary tree. The rooted tree is said to be a binary tree for m=2.

Rooted Tree

What is a Binary Search Tree?

A binary tree which satisfy the following property is said to be Binary Search Tree -

  • XX in left sub-tree of vertex V,Value(X)≤Value(V)V,Value(X)≤Value(V)
  • YY in right sub-tree of vertex V,Value(Y)≥Value(V)V,Value(Y)≥Value(V)

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 height of the binary tree is the number of links from the root node to the deepest node of the Binary Search Tree.

Example

Binary Search Tree

Algorithm to search for a key in BST

Complexity of Binary search tree

Average Case
Worst case
Space Complexity
O(n)
O(n)
Search Complexity
O(log n)
O(n)
Insertion Complexity
O(log n)
O(n)
Deletion Complexity
O(log n)
O(n)

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Discrete Mathematics Topics