UNIT-4

Trees: Basic terminology used with Tree, Binary Trees,

Binary Tree Representation: Array Representation and
Pointer (Linked List) Representation, Binary Search Tree,
Complete Binary Tree, A Extended Binary Trees, Tree
Traversal algorithms: Inorder, Preorder and Postorder,
Constructing Binary Tree from given Tree Traversal,
Operation of Insertion,
Deletion, Searching & Modification of data in Binary
Search Tree. Threaded Binary trees, Huffman coding using
Binary Tree, AVL Tree and B Tree.
Height
The height of a node is the number of edges on the longest path from that node to a
leaf node.
As such, the height of the tree would be the height of its root node. Meanwhile, the
leaf nodes have a height of 0.
Depth

The depth of a node is the number of edges from that node to the tree’s root node. As such,
the depth of the whole tree would be the depth of its deepest leaf node. The root node has a
depth of 0.

Let’s look at the following tree,

which gives the depth of each node.
Skewed Tree
A skewed tree is a tree, skewed to the left or skews to the right.
or
It is a tree consisting of only left subtree or only right subtree.
• A tree with only left subtrees is called Left Skewed Binary
Tree.
• A tree with only right subtrees is called Right Skewed
Binary Tree.
Extended Binary Tree

Extended binary tree is a type of binary tree in which all the null sub tree of the original
tree are replaced with special nodes called external nodes whereas other nodes are called
internal nodes.

Properties of External binary tree

1.The nodes from the original tree are internal

nodes and the special nodes are external nodes.
2.All external nodes are leaf nodes and the internal
nodes are non-leaf nodes.
3.Every internal node has exactly two children and
every external node is a leaf. It displays the
result which is a complete binary tree.
BINARY TREE REPRESENTATION
The storage representation of binary trees can be classified as
1. Array representation
2. Linked representation.

Array representation:
• A tree can be represented using an array, which is called sequential representation.
• The nodes are numbered from 1 to n, and one dimensional array can be used to store the
nodes.
• Position 0 of this array is left empty and the node numbered i is mapped to position i of the
array.
Below figure shows the array representation for both the trees of figure (a).
•For complete binary tree the array representation
is ideal, as no space is wasted.
•For the skewed tree less than half the array is
utilized.
Linked representation:
The problems in array representation are:
• It is good for complete binary trees, but more memory is wasted for skewed and many
other binary trees.
• The insertion and deletion of nodes from the middle of a tree require the movement of
many nodes to reflect the change in level number of these nodes.

These problems can be easily overcome by linked representation Each node has three
fields,
• LeftChild- which contains the address of left subtree
• RightChild - which contains the address of right subtree.
• Data- which contains the actual information
1 . Level-Order traversal:
Visiting the nodes using the ordering suggested by the node numbering is called level ordering
traversing.
The nodes in a tree are numbered starting with the root on level 1 and so on.
Firstly visit the root, then the root’s left child, followed by the root’s right child. Thus
continuing in this manner, visiting the nodes at each new level from the leftmost node to the
rightmost node.

Level order traversal: 1 2 3 4 5

Initially in the code for level order add the root to the queue. The function operates by
deleting the node at the front of the queue, printing the nodes data field and adding the nodes
left and right children to the queue.
Binary search tree insertion function

struct node *insert(struct node *root, int val)

{
if(root == NULL)
return getNewNode(val);
if(root->key < val)
root->right = insert(root->right,val);
else if(root->key > val)
root->left = insert(root->left,val);
return root;
}
struct node *getNewNode(int val)
{
struct node *newNode = malloc(sizeof(struct node));
newNode->key = val;
newNode->left = NULL;
newNode->right = NULL;

return newNode;
}
 if(root->key < val)
#include <stdio.h> root->right = insert(root->right,val);
#include<stdlib.h> else if(root->key > val)
struct node root->left = insert(root->left,val);
{ return root;
int key; }
struct node *left;
struct node *right; void inorder(struct node *root)
};//this function will return the new node with { if(root == NULL)
the given value return;
struct node *getNewNode(int val) inorder(root->left);
{ printf("%d ",root->key);
struct node *newNode = malloc(sizeof(struct inorder(root->right);
node)); }
newNode->key = val;
newNode->left = NULL; int main()
{ struct node *root = NULL;
newNode->right = NULL; return newNode; root = insert(root,100);
} root = insert(root,50);
root = insert(root,150);
struct node *insert(struct node *root, int val) root = insert(root,50);
{
if(root == NULL) inorder(root);
return getNewNode(val); return 0;
DELETE BST FUNCTION

struct node *removeNode(struct node *root, int val) else if(root->right == NULL)
{ {
if(root == NULL) struct node *temp = root->left;
return NULL; free(root);
if(root->key < val) return temp;
root->right = removeNode(root->right,val); }
else if(root->key > val)
root->left = removeNode(root->left,val); else
else {
{ int rightMin = getRightMin(root->right);
if(root->left == NULL && root->right == NULL) root->key = rightMin;
{ root->right = removeNode(root->
free(root); right,rightMin);
return NULL; }
}
else if(root->left == NULL) }
{
struct node *temp = root->right; //return the actual root's address
free(root); return root;
return temp; }
}
int getRightMin(struct node *root)
{
struct node *temp = root;

while(temp->left != NULL)
{
temp = temp->left;
}

return temp->key;
}
THREADED BINARY TREE: A threaded binary tree is a type of binary tree data structure
where the empty left and right child pointers in a binary tree are replaced with threads
that link nodes directly to their in-order predecessor or successor, thereby providing a
way to traverse the tree without using recursion or a stack. Threaded binary trees can be
useful when space is a concern, as they can eliminate the need for a stack during
traversal. However, they can be more complex to implement than standard binary trees.

Types of Binary Tree

• One-way threaded Binary Tree
• Two-way threaded Binary Tree
• One-way threaded Binary Tree
 In one-way threaded binary trees, a thread will appear either in the right or left
link field of a node. If it appears in the right link field of a node then it will point to
the next node that will appear on performing in order traversal. Such trees are
called Right threaded binary trees.
 If thread appears in the left field of a node then it will point to the nodes inorder
predecessor. Such trees are called Left threaded binary trees.
 In one-way threaded binary trees, the right link field of last node and left link field
of first node contains a NULL. In order to distinguish threads from normal links
they are represented by dotted lines.
Two-way threaded Binary Trees:

In two-way threaded Binary trees, the right link field of a node containing NULL
values is replaced by a thread that points to nodes inorder successor and left field
of a node containing NULL values is replaced by a thread that points to nodes
inorder predecessor.

In the above figure of two-way threaded Binary tree, we noticed that no left
thread is possible for the first node and no right thread is possible for the last
node. This is because they don't have any inorder predecessor and successor
respectively. This is indicated by threads pointing nowhere.
Advantages of Threaded Binary Tree:
•In threaded binary tree, linear and fast traversal of nodes in the tree so there is no
requirement of stack. If the stack is used then it consumes a lot of memory and time.
•It is more general as one can efficiently determine the successor and predecessor of any
node by simply following the thread and links. It almost behaves like a circular linked
list.
Disadvantages of Threaded Binary Tree:
•When implemented, the threaded binary tree needs to maintain the extra information for
each node to indicate whether the link field of each node points to an ordinary node or
the node's successor and predecessor.
•Insertion into and deletion from a threaded binary tree are more time consuming since
both threads and ordinary links need to be maintained.
HUFFMAN CODING: Huffman coding is a lossless data compression
algorithm. The idea is to assign variable-length codes to input characters,
lengths of the assigned codes are based on the frequencies of corresponding
characters. The most frequent character gets the smallest code and the least
frequent character gets the largest code.
The variable-length codes assigned to input characters are Prefix Codes,
means the codes (bit sequences) are assigned in such a way that the code
assigned to one character is not the prefix of code assigned to any other
character. This is how Huffman Coding makes sure that there is no ambiguity
when decoding the generated bit stream.
Let us understand prefix codes with a counter example. Let there be four
characters a, b, c and d, and their corresponding variable length codes be 00,
01, 0 and 1. This coding leads to ambiguity because code assigned to c is the
prefix of codes assigned to a and b. If the compressed bit stream is 0001, the
de-compressed output may be “cccd” or “ccb” or “acd” or “ab”.
 There are mainly two major parts in Huffman Coding
• Build a Huffman Tree from input characters.
• Traverse the Huffman Tree and assign codes to characters.

Steps to build Huffman Tree

• Input is an array of unique characters along with their frequency of occurrences
and output is Huffman Tree.

• Create a leaf node for each unique character and build a min heap of all leaf
nodes (Min Heap is used as a priority queue. The value of frequency field is used
to compare two nodes in min heap. Initially, the least frequent character is at root)
• Extract two nodes with the minimum frequency from the min heap.
•
• Create a new internal node with a frequency equal to the sum of the two nodes
frequencies. Make the first extracted node as its left child and the other extracted
node as its right child. Add this node to the min heap.
Time Complexity- O(n log n)
a= 0
b=101
c = 100
d=111
e =1101
f= 1100
AVL Tree

• AVL Tree is invented by GM Adelson - Velsky and EM Landis in 1962. The tree is
named AVL in honour of its inventors.
• AVL Tree can be defined as height balanced binary search tree in which each node is
associated with a balance factor which is calculated by subtracting the height of its right
sub-tree from that of its left sub-tree.
• Tree is said to be balanced if balance factor of each node is in between -1 to 1,
otherwise, the tree will be unbalanced and need to be balanced.
• Balance Factor (k) = height (left(k)) - height (right(k))

The tree is AVL because the differences between

the heights of left and right subtrees for every node
are less than or equal to 1.
• If balance factor of any node is 1, it means that the left sub-tree is one level higher
than the right sub-tree.
• If balance factor of any node is 0, it means that the left sub-tree and right sub-tree
contain equal height.
• If balance factor of any node is -1, it means that the left sub-tree is one level lower
than the right sub-tree.
 Complexity
Algorithm Average case Worst case
Space o(n) o(n)
Search o(log n) o(log n)
Insert o(log n) o(log n)
Delete o(log n) o(log n)

Why AVL Tree?

AVL tree controls the height of the binary search tree by not letting it to be skewed.
The time taken for all operations in a binary search tree of height h is O(h). However,
it can be extended to O(n) if the BST becomes skewed (i.e. worst case). By limiting
this height to log n, AVL tree imposes an upper bound on each operation to be O(log n)
where n is the number of nodes.
Operations on an AVL Tree:
• Insertion
• Deletion
• Searching [It is similar to performing a search in BST]

AVL Rotations

1. L L rotation : Inserted node is in the left subtree of left subtree of critical node
2. R R rotation : Inserted node is in the right subtree of right subtree of critical node
3. L R rotation : Inserted node is in the right subtree of left subtree of critical node
4. R L rotation : Inserted node is in the left subtree of right subtree of critical node
1. RR Rotation
When BST becomes unbalanced, due to a node is inserted into the right subtree of the right
subtree of A, then we perform RR rotation, RR rotation is an anticlockwise rotation, which is
applied on the edge below a node having balance factor -2
2. LL Rotation
When BST becomes unbalanced, due to a node is inserted into the left subtree of the left
subtree of C, then we perform LL rotation, LL rotation is clockwise rotation, which is
applied on the edge below a node having balance factor 2.
3. LR Rotation
LR rotation = RR rotation + LL rotation, i.e., first RR rotation is performed on subtree
and then LL rotation is performed on full tree, by full tree we mean the first node from
the path of inserted node whose balance factor is other than -1, 0, or 1.
4. RL Rotation
R L rotation = LL rotation + RR rotation, i.e., first LL rotation is performed on
subtree and then RR rotation is performed on full tree, by full tree we mean the
first node from the path of inserted node whose balance factor is other than -1, 0,
or 1.
Q1.

Insert the following in AVL Tree-

Q2.
27, 82,67,97,84,1,7,9,12,99
 B-TREE
• B-Tree is a self-balancing search tree.
• In most of the other self-balancing search trees (like AVL and Red-Black Trees), it
is assumed that everything is in main memory.
• To understand the use of B-Trees, we must think of the huge amount of data that
cannot fit in main memory. When the number of keys is high, the data is read from
disk in the form of blocks. Disk access time is very high compared to the main
memory access time.
• The main idea of using B-Trees is to reduce the number of disk accesses. Most of
the tree operations (search, insert, delete, max, min, ..etc ) require O(h) disk
accesses where h is the height of the tree.
• B-tree is a fat tree. The height of B-Trees is kept low by putting maximum
possible keys in a B-Tree node.
• Generally, the B-Tree node size is kept equal to the disk block size. Since the
height of the B-tree is low so total disk accesses for most of the operations are
reduced significantly compared to balanced Binary Search Trees like AVL Tree,
Red-Black Tree, ..etc.
Properties of B-Tree:

• All leaves are at the same level.

• A B-Tree is defined by the term minimum degree ‘t’. The value of t depends upon
disk block size.
• All nodes (excluding root) may contain at most t-1 keys and at least t/2 keys.
• Number of children of a node is equal to the number of keys in it plus 1.
• Every node in the B-Tree except the root node and leaf nodes has at least (minimum)
t/2 children and has maximum t children.
• The root node has at least two children if it is not a terminal (leaf ) node.
• All keys of a node are sorted in increasing order. The child between two keys k1 and
k2 contains all keys in the range from k1 and k2.
• B-Tree grows and shrinks from the root which is unlike Binary Search Tree. Binary
Search Trees grow downward and also shrink from downward.
• Like other balanced Binary Search Trees, time complexity to search, insert and delete
is O(log n).
• Insertion of a Node in B-Tree happens only at Leaf Node.