UNIT III NON-LINEAR DATA STRUCTURES - TREES

Tree ADT - tree traversals - Binary Tree ADT - expression trees - applications of trees - binary search tree ADT -
Threaded Binary Trees- AVL Trees - B-Tree - B+ Tree - Heap - Applications of heap
2MARKS
1. Define tree?
Trees are non-liner data structure, which is used to store data items in a shorted sequence.
It represents any hierarchical relationship between any data Item. It is a collection of nodes, which has a
distinguish node called the root and zero or more non-empty sub trees T1, T2,….Tk. each of which are
connected by a directed edge from the root.
2. Define Height of tree?
The height of n is the length of the longest path from root to a leaf. Thus all leaves have height zero. The
height of a tree is equal to a height of a root.
3. Define Depth of tree?
For any node n, the depth of n is the length of the unique path from the root to node n.
Thus for a root the depth is always zero.
4. What is the length of the path in a tree?
The length of the path is the number of edges on the path. In a tree there is exactly one path form the root
to each node.
5. Define sibling?
Nodes with the same parent are called siblings. The nodes with common parents are called siblings.
6. Define binary tree?
A Binary tree is a finite set of data items which is either empty or consists of a single item called root and
two disjoin binary trees called left sub tree max degree of any node is two.
7. of tree data-structure?
Ø The manipulation of Arithmetic expression Ø Used for
Searching Operation
Ø Used to implement the file system of several popular operating systems Ø Symbol Table
construction
Ø Syntax analysis
8. Define expression tree?
Expression tree is also a binary tree in which the leafs terminal nodes or operands and non-terminal
intermediate nodes are operators used for traversal.
9. Define tree– traversal and mention the type of traversals?
Visiting of each and every node in the tree exactly is called as tree traversal. Three types of tree
traversal
1. Inorder traversal
2. Preoder traversal
3. Postorder traversal.
10. Define threaded binary tree.
A binary tree is threaded by making all right child pointers that would normally be null point to the in order
successor of the node, and all left child pointers that would normally be null point to the in order predecessor of the
node.
11. What are the types of threaded binary tree?
i. Right-in threaded binary tree
ii. Left-in threaded binary tree
iii. Fully-in threaded binary tree
12. Define Binary Search Tree.
Binary search tree is a binary tree in which for every node X in the tree, the values of all the keys in its left subtree
are smaller than the key value in X and the values of all the keys in its right subtree are larger than the key value in
X.
13. What is AVL Tree?
AVL stands for Adelson-Velskii and Landis. An AVL tree is a binary search tree which has the following properties:
1. The sub-trees of every node differ in height by at most one.
2. Every sub-tree is an AVL tree.
Search time is O(logn). Addition and deletion operations also take O(logn) time.
14. What is ‘B’ Tree?
A B-tree is a tree data structure that keeps data sorted and allows searches, insertions, and deletions in
logarithmic amortized time. Unlike self-balancing binary search trees, it is optimized for systems that read and write
large blocks of data. It is most commonly used in database and file systems.
15. Define complete binary tree.
If all its levels, possible except the last, have maximum number of nodes and if all the nodes in the last level
appear as far left as possible
BIG QNS
1. Write an algorithm for preorder, inorder and postorder traversal of a binary tree.
Displaying (or) visiting order of nodes in a binary tree is called as Binary Tree Traversal.
There are three types of binary tree traversals.
1. In - Order Traversal
2. Pre - Order Traversal
3. Post - Order Traversal
1. In-order Traversal
In this traversal method, the left subtree is visited first, then the root and later the right sub-tree.
We start from A, and following in-order traversal, we move to its left subtree B. B is also traversed in-order. The
process goes on until all the nodes are visited. The output of inorder traversal of this tree will be −
D→B→E→A→F→C→G
void inorder(node T)
1. Traverse the left subtree, {
i.e., call Postorder(left- if(T!=NULL)
subtree) {
2. Visit the root. inorder(T->left);
3. Traverse the right subtree, printf("%d \t",T-
i.e., call Postorder(right- >data);
subtree) inorder(T->right);
}}

2. Pre-order Traversal
In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.
A→B→D→E→C→F→G
Algorithm Preorder (tree) Coding:
1. Visit the root. void preorder(node T)
{
2. Traverse the left subtree, i.e., call if(T!=NULL)
Preorder(left-subtree) {
printf("%d \t",T-
3. Traverse the right subtree, i.e., call >data);
Preorder(right-subtree) preorder(T->left);
preorder(T->right);}}
 3. Post order traversal
In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree,
then the right subtree and finally the root node.
The output of post-order traversal of this tree will be −
D→ E → B → F → G → C → A
Algorithm Postorder(tree) Coding
1. Traverse the left subtree, void postorder(node T)
i.e., call Postorder(left- {
subtree) if(T!=NULL)
2. Traverse the right subtree, {
i.e., call Postorder(right- postorder(T->left);
subtree) postorder(T->right);
3. Visit the root. printf("%d \t",T->data);}
}

2. Write an algorithm for create an Expression Tree.

Expression tree is a binary tree in which the leaf nodes are operands and the interior nodes are operators.
Construction of expression tree
Step 1 : Convert infix to postfix
Step 2 : We read our expression one symbol at a time.
If the symbol is an operand, we create a one node tree and push a pointer to it onto a
stack.
If the symbol is an operator, we pop pointers to two trees T 1 and T 2 from the stack (T 1 is popped first) and
form a new tree whose root is the operator and whose left and right children point to T 2 and T 1 respectively.
A pointer to this new tree is then pushed onto the stack.
Example 1:
3 + ((5+9)*2)

Example 2:
As an example, suppose the input is a b + c d e + * * The first two symbols are operands, so we
create one-node trees and push pointers to them onto a stack.* *For convenience, we will have the stack
grow from left to right in the diagrams.
 3. Write an algorithm for inserting and deleting a node in a binary search tree.
Binary Search Tree is a binary tree in which every node contains only smaller values in its left subtree and only larger
values in its right subtree. Every binary search tree is a binary tree but every binary tree need not to be binary search tree.
Operations
 Insertion()
 Deletion()
 Searching ()
 Find min()
 Find Max()

Insertion Operation in BST

Step 1 - Create a newNode with given value and set its left and right to NULL.
Step 2 - Check whether tree is Empty.
Step 3 - If the tree is Empty, then set root to newNode.
Step 4 - If the tree is Not Empty, then check whether the value of newNode is smaller or larger than the node
(here it is root node).
Step 5 - If newNode is smaller than or equal to the node then move to its left child. If newNode is larger than
the node then move to its right child.
Step 6- Repeat the above steps until we reach to the leaf node (i.e., reaches to NULL).
Step 7 - After reaching the leaf node, insert the newNode as left child if the newNode is smaller or equal to
that leaf node or else insert it as right child.

Routine
Tree* insert(Tree *L)
Example {
Construct a Binary Search Tree by inserting the Tree *t1,*t2;
if(L==NULL)
following sequence of numbers... {
10,12,5,4,20,8,7,15 and 13 printf("\nEnter Data:");
Above elements are inserted into a Binary Search scanf("%d",&d);
Tree as follows... L=makeNode(d);
}
else
{
printf("\nEnter Data:");
scanf("%d",&d);
t1=L;
t2=L;
while(d!=t1->reg&&t2!=NULL)
{
t1=t2;
if(d<t1->reg)
t2=t1->left;
if(d>t1->reg)
t2=t1->right;
}
if(d==t1->reg)
{
printf("\n Data Already There\n");
}
else
{
if(d<t1->reg)
t1->left=makeNode(d);
if(d>t1->reg)
t1->right=makeNode(d);
}
}
return L;
}
Deletion Operation in BST
Case 1: Deleting a leaf node
Step 1 - Find the node to be deleted using
search operation
Step 2 - Delete the node using free function
(If it is a leaf) and terminate the function.
Case 2: Deleting a node with one child
Step 1 - Find the node to be deleted using
search operation
Step 2 - If it has only one child then create a
link between its parent node and child
node.
Step 3 - Delete the node using free function
and terminate the function.
Case 3: Deleting a node with two children
Step 1 - Find the node to be deleted using
search operation
Step 2 - If it has two children, then find the
largest node in its left subtree (OR) the
smallest node in its right subtree.
Step 3 - Swap both deleting node and node
which is found in the above step.
Step 4 - Then check whether deleting node
came to case 1 or case 2 or else goto step if(d<L->reg)
2 L->left=deleteNode(L->left,d);
Step 5 - If it comes to case 1, then delete using else if(d>L->reg)
case 1 logic. L->right=deleteNode(L->right,d);
Step 6- If it comes to case 2, then delete using else if(L->left&&L->right)
case 2 logic. {
q=findMin(L->right);
Step 7 - Repeat the same process until the L->reg=q->reg;
node is deleted from the tree. L->right=deleteNode(L->right,L->reg);
Routine }
Tree* deleteNode(Tree *L,int d) else
{ {
Tree *q; q=L;
if(L==NULL) if(L->left==NULL)
{ L=L->right;
printf("\nDelete Element Not Found !!!\n\n"); if(L->right==NULL)
} L=L->left;
else{ free(q);
printf("\nElement Deleted Successfully\n\n");
}}
return L}
4 .Explain an AVL TREES with its operations and rotations.
 An AVL tree is a self balanced binary search tree.
 A binary tree is said to be balanced, if the difference between the heights of left and right subtrees of every
node in the tree is either -1, 0 or +1
 Balance factor of a node is the difference between the heights of left and right subtrees of that node. Balance
factor = height Of Left Subtree – height Of Right Subtree
AVL Tree Rotations
Rotation is the process of moving the nodes to either left or right to make tree balanced.
There are four rotations and they are classified into two types.
 Single Rotation -Left Left Rotation, Right Right Rotation
 Double Rotation -Left Right Rotation , Right Left Rotation
Single Left Rotation (LL
Rotation)
In RR Rotation every node moves
one position to right from the
current position. To understand RR
Rotation, let us consider following
insertion operations into an AVL
Tree...
Single Right Rotation (RR
Rotation)
In LL Rotation every node moves
one position to left from the current
position. To understand LL
Rotation, let us consider following
insertion operations into an AVL
Tree...
Left Right Rotation (LR
Rotation)
The LR Rotation is combination of
single left rotation followed by
single right rotation

Right Left Rotation (RL

Rotation)
The RL Rotation is combination
of single right rotation followed
by single left rotation

.
 .
Operations on an AVL Tree
[Link] Operation in AVL Tree
In an AVL tree, the insertion operation is performed with O(log n) time complexity. In AVL Tree, new node is
always inserted as a leaf node. The insertion operation is performed as follows...
 Step 1: Insert the new element into the tree using Binary Search Tree insertion logic.
 Step 2: After insertion, check the Balance Factor of every node.
 Step 3: If the Balance Factor of every node is 0 or 1 or -1 then go for next operation.
 Step 4: If the Balance Factor of any node is other than 0 or 1 or -1 then tree is said to be imbalanced. Then
perform the suitable Rotation to make it balanced. And go for next operation.
Example: Construct an AVL Tree by inserting numbers from 1 to 8.
Example: Construct an AVL Tree by inserting numbers from 1 to 8.

Deletion Operation in AVL Tree

 Step 1:
 The node to be deleted from the tree is 8.
 If we observe it is the parent node of the
node 5 and 9.
 Since the node 8 has two children it can be
replaced by either of it’s child nodes.

Step 2:
 The node 8 is deleted from the tree.
 As the node is deleted we replace it with either of
it’s children nodes.
 Here we replaced the node with the inorder
successor , i.e, 9.
 Again we check the balance factor for each node.

Step 3:
 Now The next element to be deleted is 12.
 If we observe, we can see that the node 12 has a
left subtree and a right subtree.
 We again can replace the node by either it’s
inorder successor or inorder predecessor.
 In this case we have replaced it by the inorder
successor.

Step 4:
 The node 12 is deleted from the tree.
 Since we have replaced the node with the inorder
successor, the tree structure looks like shown in the
image.
After removal and replacing check for the balance
factor of each node of the tree.

Step 5:
 The next node to be eliminated is 14.
 It can be seen clearly in the image that 14 is a leaf
node.
 Thus it can be eliminated easily from the tree.

Step 6:
 As the node 14 is deleted, we check the balance
factor of all the nodes.
 We can see the balance factor of the node 13 is 2.
 This violates the terms of the AVL tree thus we
need to balance it using the rotation mechanism.
 5. Explain B Tree with an example.

B-Tree is a self-balanced search tree with multiple keys in every node and more than two children for
every node. Here, number of keys in a node and number of children for a node is depending on the order
of the B-Tree. Every B-Tree has order.
B-Tree of Order m has the following properties...

 Property #1 - All the leaf nodes must be at same level.

 Property #2 - All nodes except root must have at least [m/2]-1 keys and maximum of m- 1 keys.
 Property #3 - All non-leaf nodes except root (i.e. all internal nodes) must have at least m/2 children.
 Property #4 - If the root node is a non-leaf node, then it must have at least 2 children.
 Property #5 - A non-leaf node with n-1 keys must have n number of children.
 Property #6 - All the key values within a node must be in Ascending Order.

Operations on a B-Tree.
Insertion Operation in B-Tree
 Step 1: Check whether tree is Empty.
 Step 2: If tree is Empty, then create a new node with new key value and insert into the tree as a root node.
 Step 3: If tree is Not Empty, then find a leaf node to which the new key value cab be added using Binary
Search Tree logic.
 Step 4: If that leaf node has an empty position, then add the new key value to that leaf node by maintaining
ascending order of key value within the node.
 Step 5: If that leaf node is already full, then split that leaf node by sending middle value to its parent node.
Repeat the same until sending value is fixed into a node.
 Step 6: If the splitting is occurring to the root node, then the middle value becomes new root node for the
tree and the height of the tree is increased by one.
Example 2: Inserting the sequence 9,0,8,1,7,2,6,3,5,4 into a B-Tree.
Deletion
First, if the item you are deleting is not in a leaf node, then bring its predecessor up into its space and delete
the predecessor item from its leaf node. This may require transfers and fusions. Fusions may cause underflow
at the parent so in general this process has to be repeated up the tree.
A simple deletion example, requiring transfers only:

6. Explain B+ Tree with an example .

 B+ Tree is an extension of B Tree which allows efficient insertion, deletion and search
operations.
 In B Tree, Keys and records both can be stored in the internal as well as leaf nodes.
  The internal nodes of B+ tree are often called index nodes. A B+ tree of order 3 is shown in the
following figure.

B Tree VS B+ Tree

B Tree B+ Tree
Search keys can not be repeatedly stored. Redundant search keys can be present.
Data can be stored in leaf nodes as well as Data can only be stored on the leaf
internal nodes nodes.
Searching for some data is a slower Searching is comparatively faster as
process since data can be found on data can only be found on the leaf
internal nodes as well as on the leaf nodes.
nodes.
Deletion of internal nodes are so Deletion will never be a complexed
complicated and time consuming. process since element will always be
deleted from the leaf nodes.
Leaf nodes can not be linked together. Leaf nodes are linked together to make
the search operations more efficient.
Insertion in B+ Tree
Step 1: Insert the new node as a leaf node
Step 2: If the leaf doesn't have required space, split the node and copy the middle node to the next index
node.
Step 3: If the index node doesn't have required space, split the node and copy the middle element to the
next index page.
Example :

Deletion in B+ Tree
Step 1: Delete the key and data from the leaves.
Step 2: if the leaf node contains less than minimum number of elements, merge down the node with its
sibling and delete the key in between them.
Step 3: if the index node contains less than minimum number of elements, merge the node with the sibling
and move down the key in between them.
 [Link] is a Heap? How percolate up and down operations will be performed on a heap?
Heap data structure is a specialized binary tree based data structure. Heap is a binary tree with special
characteristics. In a heap data structure, nodes are arranged based on their value. A heap data structure,
sometime called as Binary Heap. There are two types of heap data structures and they are as follows...
1. Max Heap
2. Min Heap

Every heap data structure has the following properties...

Property #1 (Ordering): Nodes must be arranged in a order according to values based on Max heap or Min
heap.
Property #2 (Structural): All levels in a heap must full, except last level and nodes must be filled from
left to right strictly.

Insertion Operation in max heap is performed as follows...

 Step 1 − Create a new node at the end of heap.
 Step 2 − Assign new value to the node.
 Step 3 − Compare the value of this child node with its parent.
 Step 4 − If value of parent is less than child, then swap them.
 Step 5 − Repeat step 3 & 4 until Heap property holds.

Example
 Deletion Operation in Max Heap
In a max heap, deleting last node is very simple as it is not disturbing max heap properties.
Deleting root node from a max heap is title difficult as it disturbing the max heap properties. We use the
following steps to delete root node from a max heap...
 Step 1 − Remove root node.
 Step 2 − Move the last element of last level to root.
 Step 3 − Compare the value of this child node with its parent.
 Step 4 − If value of parent is less than child, then swap them.
 Step 5 − Repeat step 3 & 4 until Heap property holds.
 Min-Heap − Where the value of the root node is less than or equal to either of its children.
Insertion Algorithm
To add an element to a heap we must perform an up-heap operation (also known as bubble-up, percolate-
up, sift-up trickle-up, heapify-up, or cascade-up), by following this algorithm:
 If heap is empty place element at root.
 Add the element to the bottom level of the heap.
 Compare the added element with its parent; if they are in the correct order, stop.
 If not, swap the element with its parent and return to the previous step.

Deletion Algorithm:
1. Delete the node that contains the value you want deleted in the heap.
2. Replace the deleted node with the farthest right node.
3. Heapify (Fix the heap):
if the heap property holds true
then you are done.
else if the replacement node value <= its parent nodes value
then swap them, and repeat step 3.
else
swap the replacement node with the smallest child node, and
repeat step 3.