Unit-IV

TREES & GRAPHS

 Trees
• It is a non-linear data structure.
• This structure is used to represent data
containing a hierarchical relationship between
elements.
 Binary Tree
• A binary tree T is defined as a finite set of elements called nodes such that:
– T is empty (called null tree of empty tree)
– T contains a distinguished node R, called root of T, and the remaining nodes of T
form an ordered pair of disjoint binary trees T 1 and T2.

• If T contains a root R,
– T1 is called the left successor of R.
– T2 is called the right successor of R.

• The nodes with no successors are called terminal nodes.

• Binary trees T and T’ are said to be similar if they have the same structure
(or same shape).

• The trees are said to be copies if they are similar and having the same
contents at the corresponding nodes.
Example
 Terminology
• Suppose N is a node in T with left successor S 1 and right successor
S2.
– N is called the parent (or father) of S1 and S2.
– S1 is the left child (or son) of N.
– S2 is the right child (or son) of N.
– S1 and S2 are said to be siblings (or brothers).

• Every node N in a binary tree T, except the root, has a unique

parent, called the predecessor of N.

• If there is a succession of children from node N to node L,

– Node L is called the descendant of node N.
– Node N is called the ancestor of node L.
 Terminology
• The line drawn from node N to a successor is called and edge.
• Sequence of consecutive edges is a path.
• A terminal node is called a leaf.
• A path ending in a leaf is called branch.

• Each node in a binary tree T is assigned a level number as:

– Root node is at level 0
– Every node is assigned a level number which is one more than level number
of its parent.

• Nodes with same level number are said to belongs to same generation.

• Depth or Height of a tree T is the maximum number of nodes in a

branch of T.
– It is one more than the largest level number of T.
 Complete Binary Tree
• Consider a binary tree T, each node can have at most
two children.

• The 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.

• All the nodes at the last level should appear as far left
as possible.
• The nodes is above fig. are labeled by integers from left to
right, generation by generation.

• To determine the children and parent of any node K in tree Tn:

– Left child of node K is 2*K
– Right child of node K is 2*K+1
– Parent of K is node └K/2 ┘.

• The depth dn of complete tree Tn with n nodes is given by:

– Dn = └ log2n+1 ┘
 Extended Binary Tree or 2-Tree
• A binary tree T is said to be a 2-Tree or
extended binary tree if each node N has
either 0 or 2 children.
• The nodes with 2 children are called internal
nodes.
• The nodes with 0 children are called external
nodes.
Binar y Tree T Extended 2-Tree
 Example of 2-Tree
• Consider the algebraic expression E which uses only
binary operations:
– The variables in E will appear as external nodes.
– The operations in E will appear as internal nodes
Memory Representation of Binary Trees
• Binary trees can be represented in memory in
two ways:
• Linked representation
• Sequential representation
 Linked representation
• Consider a binary tree T.
• There will three parallel arrays as:
– INFO[K] contains the data at node N
– LEFT[K] contains the location of left child of node N.
– RIGHT[K] contains the location of right child of node N.

• A pointer variable ROOT contains the root R of T.

• If any subtree is empty,

– corresponding pointer will contain Null value.

• If tree T is empty,
– ROOT will contain Null value.
Linked Representation of Tree
 Sequential representation of Binary Trees

• This representation uses a single linear array TREE as

follows:
– The root R of T is stored in TREE[1]
– If a node occupies TREE[K],
• its left child is stored in TREE[2*K]
• Its right child is stored in TREE[2*K+1]

• NULL is used to indicate an empty subtree

• TREE[1]=NULL indicates that the tree is empty.

• The sequential representation of a tree with depth d will

require an array with approx 2d+1 elements.
Example
 Trees Traversal
There are three standard ways of traversing
binary tree T with root R:
• Pre-order Traversal
• In-order Traversal
• Post-order Traversal
 Pre-order Traversal
• Process the root R
• Traverse the left subtree of R in preorder
• Traverse the right subtree of R in preorder

• Also called NLR traversal.

 Inorder Traversal
• Traverse the left subtree of R in inorder
• Process the root R
• Traverse the right subtree of R in in-order

• Also called LNR traversal.

 Postorder
• Traverse the left subtree of R in post-order
• Traverse the right subtree of R in post-order
• Process the root R

• Also called LRN traversal.

 Example Tree

• Preorder Traversal
– ABDECF

• In-order Traversal
– DBEACF

• Post-order Traversal
– DEBFCA
 Example

Preorder : A B D E F C G H J L K
Inorder : D B F E A G C L J H K
Postorder : D F E B G L J K H C A
Pre-order : * + a – b c / - d e - + f g h
Post-order : a b c - + d e – f g + h - / *
Preorder Traversal
Algorithm: Preorder
In-order Traversal
Algorithm: In-order
Post-order Traversal
Algorithm: Post-order
 Binary Search Tree
T is called a binary search tree if each node N has the
following property:
– The value at N is greater than every value in the left subtree
of N and is less than every value in the right subtree of N.
– According to this property, in-order traversal of T will be a
sorted list of elements.
 Searching & Inserting in BST
• To find the location of ITEM in binary search tree T or to
insert ITEM as a new node in its appropriate place:

– Compare ITEM with the root node N of the tree.

• If ITEM < N, proceed to the left child of N.
• If ITEM >= N, proceed to the right child of N.

– Repeat above step until one of the following occurs:

• A node N is found such that ITEM=N
– which indicates successful search.
• An empty subtree is found
– which indicates unsuccessful search
– Insert ITEM in place of empty subtree.
 Deletion from a BST
There can be three cases:
• Case 1.
– N has no children.
– N is deleted from T by replacing location of N in P(N) by null
pointer
• Case 2.
– N has exactly one child.
– Replace the location of N in P(N) by location of only child of N.
• Case 3. N has two children.
– Let S(N) denote the in order successor of N.
– First delete S(N) from T
– Replace node N in T by S(N).
Example
 Algorithm: Case 1 or Case 2
CASEA(INFO, LEFT, RIGHT, ROOT, LOC, PAR)
This procedure deletes the node N at location LOC, where N does not have two
children. The pointer PAR gives the location of the parent of N, or else PAR=NULL
indicates that N is the root node. The pointer CHILD gives the location of the only
child of N, or else CHILD=NULL indicates that N has no children.
 AVL Search Trees
• An empty binary tree is an AVL Tree.
• A non empty binary tree T is an AVL tree iff
given TL and TR be the left and right subtrees
of T and HL and HR be the heights of respective
subtrees, (HL-HR)<=1 known as Balance factor
(BF) which can be either 0, 1, -1.
Representation of AVL Search Tree
 Insertion in an AVL Tree
• LL Rotation
– Inserted node is in the left subtree of left subtree of node A
• RR Rotation
– Inserted node is in the right subtree of right subtree of node
A
• LR Rotation
– Inserted node is in the right subtree of left subtree of node A
• RL Rotation
– Inserted node is in the left subtree of right subtree of node A
LL Rotation
RR Rotation
LR Rotation
 Example
• Construct an AVL Tree with following nodes:
40, 20, 10, 25, 30, 22, 50
Deletion in an AVL Tree
 m-Way Search Tree
• For some integer m, known as order of the
tree, each node is of degree which can reach a
maximum of m, or in other words, each node
has at most m child nodes.
• If node has k child nodes where k<=m, then
node can have only (k-1) keys partitioning all
the keys in the subtrees into k subsets.
5-way search tree
Insertion in an m-Way Search Tree
Deletion in an m-Way Search Tree
Example
 B-Tree
• A B-Tree is a balanced m-Way Search Tree
• A B-Tree of order m, if non-empty, is an m-
Way search tree in which:
– The root has at least two child nodes and at most
m child nodes.
– The internal nodes except the root have at least
m/2 child nodes and at most m child nodes.
– All leaf nodes are on the same level.
B-Tree of order 5
Insertion
Deletion
 Example
• Construct a B-Tree with following nodes:
10, 20, 40, 50, 60, 70, 80, 30, 35, 5, 15