International Islamic University Chittagong

Department of Computer Science & Engineering

Spring - 2021

Course Code: CSE-2321

Course Title: Data Structures

Mohammed Shamsul Alam

Professor, Dept. of CSE, IIUC
Lecture – 14

Tree
 Tree
A tree is a very important non linear data structure as it is useful in many
applications. A tree structure is a method of representing the hierarchical
nature of a structure in a graphical form. It is termed as "tree structure" since its
representation resembles a tree. However, the chart of a tree is normally
upside down compared to an actual tree, with the root at the top and the
leaves at the bottom.
The figure 10.1 depicts a tree structure, which represents the hierarchical
organization of books.

In the hierarchical organization of books shown in figure 10.1, Books is the root
of the tree. Books can be classified as Fiction and Non-fiction. Non-fiction
books can be further classified as Realistic and Non-realistic, which are the
leaves of the tree. Thus, it forms a complete tree structure.
3
 Binary Tree
A binary tree is a tree in which each node can have at most two children.
A binary tree is either empty or consists of a node called the root together
with two binary trees called the left subtree and the right subtree.
A tree with no nodes is called as a null tree.

A Binary Tree T is defined as finite set of elements, called nodes, such that:
a) T is empty (called the null tree or empty tree.)
b) 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.
If T does contain a root R, then the two trees T1 and T2 are called, respectively,
the left sub tree and right sub tree of R. If T1 is non empty, then its root is
called the left successor of R; similarly, if T2 is non empty, then its root is
called the right successor of R. The nodes with no successors are called the
terminal nodes. 4
 Tree Terminology
If N is a node in T with left successor S1 and right successor S2, then
N is called the parent(or father) of S1 and S2. Analogously, S1 is
called the left child (or son) of N, and S2 is called the right child (or
son) of N. Furthermore, S1 and S2 are said to siblings (or brothers).
Every node in the binary tree T, except the root, has a unique
parent, called the predecessor of N.
The terms descendant and ancestor have their usual meaning. A
node L is called a descendant of a node N (and N is called an
ancestor of L) if there I a succession of children from N to L.
The line drawn from a node N of T to a successor is called an edge,
and a sequence of consecutive edges is called a path. A terminal
node is called a leaf, and a path ending in a leaf is called a branch.
Each node in binary tree T is assigned a level number, as follows. The root
R of the tree T is assigned the level number 0, and every other node is
assigned a level number which is 1 more than the level number of its parent.
The maximum number of nodes at any level is 2n. Those nodes with the
same level number are said to belong to the same generation.
The depth (or height) of a tree T is the maximum number of nodes in a
branch of T. This turns out to be 1 more than the largest level number of T.
5
 Tree Terminology

Binary Trees T and T’ are said to be similar if they have the same structure or, in
other words, if they have the same shape. The trees are said to be copies if they
are similar and if they have the same contents at corresponding nodes.

6
 Tree Terminology
Full Binary tree
A full binary tree of height h has all its leaves at level h. Alternatively; All non
leaf nodes of a full binary tree have two children, and the leaf nodes have no
children. A full binary tree with height h has 2h - 1 nodes.

Complete Binary Tree:

Consider a binary tree T. 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.

Extended Binary Tree / 2-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 2 children are called
internal nodes, and the node with 0 children are called external node.
7
 Representing Binary Trees in Memory
Let T be a binary tree. Here we will discuss two ways of representing T
in memory-
I.Linked Representation of Binary Tree

II.Sequential Representation of Binary Tree

Linked Representation of Binary Tree

8
 Representing Binary Trees in Memory
.

9
 Representing Binary Trees in Memory
Sequential Representation of Binary Tree

10
 Representing Binary Trees in Memory
Array representation is good for complete binary tree, but it is
wasteful for many other binary trees. The representation suffers
from insertion and deletion of node from the middle of the tree, as it
requires the moment of potentially many nodes to reflect the change
in level number of this node. To overcome this difficulty we
represent the binary tree in linked representation.
The advantage of using linked representation of binary tree is that:
Insertion and deletion involve no data movement and no movement
of nodes except the rearrangement of pointers.
The disadvantages of linked representation of binary tree includes:
Given a node structure, it is difficult to determine its parent node.
Memory spaces are wasted for storing NULL pointers for the
nodes, which have no subtrees.

11
 Traversing Binary Trees
A traversal of a tree T is a systematic way of accessing or visiting all
the node of T. There are three standard ways of traversing a binary tree
T with root R. these are :
1. Preorder (N L R):
a) Process the node/root.
b) Traverse the Left sub tree.
c) Traverse the Right sub tree.
2. Inorder (L N R):
a) Traverse the Left sub tree.
b) Process the node/root.
c) Traverse the Right sub tree.
3. Postorder (L R N):
a) Traverse the Left sub tree.
b) Traverse the Right sub tree.
c) Process the node/root.

12
 Traversing Binary Trees
.

13
 Preparing a Tree from an infix arithmetic expression
.

14
 Formation of Binary Tree from its Traversal
Sometimes it is required to construct a binary tree if its traversals
are known. From a single travers al it is not possible to construct
unique binary tree. However, if two traversals is given then
corresponding tree can be drawn uniquely.
The basic principle for formulation is as follows:
If the preorder traversal is given, then the first node is the root node.
If the postorder traversal is given then the last node is the root
node. Once the root node is identified, all the nodes in the left sub-
trees and right sub- trees of the root node can be identified. Same
technique can be applied repeatedly to form sub- trees.
It can be noted that, two traversal are essential out of which one
should be inorder traversal and another preorder or postorder;
alternatively, given preorder and postorder traversals, binary tree
cannot be obtained uniquely.

15
 Formation of Binary Tree from its Traversal
.

16
 Binary Search Tree
Suppose T is a binary tree. Then T is called a binary search tree or
binary sorted tree if each node N of T has the following property:
The value of at N (node) is greater than every value in the left sub
tree of N and is less than or equal to every value in the right sub
tree of N.

17
Searching & Inserting in Binary Search Trees

18
 Binary Search Tree
.

19
Searching & Inserting in Binary Search Trees

20
Searching & Inserting in Binary Search Trees

21
 Deleting in a Binary Search Tree
.

22
 Deleting in a Binary Search Tree
.

23
 Deleting in a Binary Search Tree
.

24
 Deleting in a Binary Search Tree
.

25
 Deleting in a Binary Search Tree
.

26