Discrete Mathematics : Tree
Abid Afsan Hamid
Lecturer
CSE Department
Northern University of Business and Technology, Khulna
1 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Tree : Graph
● A graph T is called a tree if T is connected and T has no
cycles.
● Examples of trees are shown in the following figure.
2 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Tree : Spanning Trees
● A subgraph T of a connected graph G is called a spanning
tree of G if T is a tree and T includes all the vertices of G.
Following figure shows a connected graph G and spanning
trees T1, T2, and T3 of G.
3 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Tree : Minimum Spanning Trees
● Suppose G is a connected weighted graph where each edge
of G is assigned a weight.
● Any spanning tree T of G is assigned a total weight obtained
by adding the weights of the edges in T .
● A minimal spanning tree of G is a spanning tree whose total
weight is as small as possible.
4 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Minimum Spanning Tree (Kruskal Algorithm)
● Find a minimal spanning tree of the weighted graph in the
following figure. Note that the graph has six vertices, so a
minimal spanning tree will have five edges. Algorithm-
5 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Tree : Minimum Spanning Trees
Original Graph Minimum Spanning Tree
6 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Tree : Binary Tree
● A binary tree T is defined as a finite set of elements, called
nodes, such that:
● (1) T is empty (called the null tree or empty tree), or
● (2) T contains a distinguished node R, called the root of T ,
and the remaining nodes of T form an ordered pair of disjoint
binary trees T1 and T2.
7 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Tree : Binary Tree
● If T does contain a root R, then the two trees T1 and T2 are
called, respectively, the left and right subtrees of R.
● If T1 is nonempty, then its root is called the left successor of
R; similarly, if T2 is nonempty, then its root is called the right
successor of R.
● Every node N in T has 0, 1, or 2 successors. A node with no
successors is called a terminal node or leaf node.
8 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Tree : Binary Tree
● (a) B is a left successor and C is a right successor of the root
A.
● (b) The left subtree of the root A consists of the nodes B, D, E,
and F, and the right subtree of A consists of the nodes C, G,
H, J, K, and L.
9 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Tree : Binary Tree
● (c) The nodes A, B, C, and H have two successors, the nodes
E and J have only one successor, and the nodes D, F, G, L,
and K have no successors, i.e., they are terminal nodes.
10 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Tree : Complete Binary Tree
● In binary tree T, each node can have at most two children.
Accordingly, one can show that level r of T can have at most
2r nodes.
● The tree T is said to be complete if all its levels, except
possibly the last, have the maximum number of possible
nodes, and if all the nodes at the last level appear as far left
as possible.
11 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Tree : Complete Binary Tree
● Thus there is a unique complete tree Tn with exactly n nodes.
The complete tree T26 with 26 nodes appears in the Figure.
12 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Tree : Extended Binary Tree
● A binary tree T is said to be a 2-tree or an extended binary
tree if each node N has either 0 or 2 children.
● In such a case, the nodes with two children are called internal
nodes, and the nodes with 0 children are called external
nodes.
● Sometimes the nodes are distinguished in diagrams by using
circles for internal nodes and squares for external nodes.
13 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Tree : Extended Binary Tree
14 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Tree : Traversing Binary Trees
● There are three standard ways of traversing a binary tree T
with root R. These three algorithms, called preorder, inorder,
and postorder, are as follows:
● Preorder
(1) Process the root R.
(2) Traverse the left subtree of R in preorder.
(3) Traverse the right subtree of R in preorder.
15 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Tree : Traversing Binary Trees
● Inorder
(1) Traverse the left subtree of R in inorder.
(2) Process the root R.
(3) Traverse the right subtree of R in inorder.
● Postorder
(1) Traverse the left subtree of R in postorder.
(2) Traverse the right subtree of R in postorder.
(3) Process the root R.
16 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Binary Tree : Preorder Traversal
● The preorder traversal of T processes A, traverses LT , and
traverses RT . However, the preorder traversal of LT processes
the root B, and then D and E; and the preorder traversal of RT
processes the root C and then thus ABDECF is the preorder
traversal of T.
17 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Binary Tree : Inorder Traversal
● The inorder traversal of T traverses LT processes A, and
traverses RT . However, the inorder traversal of LT processes
D, B, and then E; and the inorder traversal of RT processes C
and then F. Thus DBEACF is the inorder traversal of T.
18 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Binary Tree : Postorder Traversal
● postorder traversal of T traverses LT, traverses RT, and
processes A. However, the postorder traversal of LT,
processes D, E, and then B, and the postorder traversal of RT
processes F and then C. Accordingly, DEBFCA is the
postorder traversal of T.
19 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Binary Search Tree
● Suppose T is a binary tree. Then T is called a binary search
tree if each node N of T has the following property:
● The value of N is greater than every value in the left subtree
of N and is less than every value in the right subtree of N.
20 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Binary Search Tree
● Consider the binary tree
(a) (b)
21 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
Binary Search Tree
● Suppose we want to delete ITEM = 14 from T . First find the
node N such that N = 14. Note N = 14 has two children.
Moving right and then left, we find the inorder successor S(N)
= 18 of N. We delete S(N) = 18 by replacing it by its only child
20, then we replace N = 14 by S(N) = 18. This yields the tree
in Fig. (b).
22 CSE Department, Northern Uni. Of Business & Technology 09/04/2023
