Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
Trees – Binary Trees, binary tree representations, Huffman algorithm, Trees and their applications.
Searching – Basic searching Techniques, Tree Searching.
Trees – Binary Trees,
Binary Trees
A Binary Tree is a type of tree data structure where each node can have a maximum of two child nodes, a left child node and a right child node.
This restriction, that a node can have a maximum of two child nodes, gives us many benefits:
Algorithms like traversing, searching, insertion and deletion become easier to understand, to implement, and run faster.
Keeping data sorted in a Binary Search Tree (BST) makes searching very efficient.
Balancing trees is easier to do with a limited number of child nodes, using an AVL Binary Tree for example.
Binary Trees can be represented as arrays, making the tree more memory efficient.
Binary Trees vs Arrays and Linked Lists
Benefits of Binary Trees over Arrays and Linked Lists:
Arrays are fast when you want to access an element directly, like element number 700 in an array of 1000 elements for example. But inserting
and deleting elements require other elements to shift in memory to make place for the new element, or to take the deleted elements place, and that is
time consuming.
Linked Lists are fast when inserting or deleting nodes, no memory shifting needed, but to access an element inside the list, the list must be
traversed, and that takes time.
Binary Trees, such as Binary Search Trees and AVL Trees, are great compared to Arrays and Linked Lists because they are BOTH fast at ac -
cessing a node, AND fast when it comes to deleting or inserting a node, with no shifts in memory needed.
Types of Binary Trees
There are different variants, or types, of Binary Trees worth discussing to get a better understanding of how Binary Trees can be structured.
The different kinds of Binary Trees are also worth mentioning now as these words and concepts will be used later in the tutorial.
Below are short explanations of different types of Binary Tree structures, and below the explanations are drawings of these kinds of structures to make it as easy to understand as possible.
A balanced Binary Tree has at most 1 in difference between its left and right subtree heights, for each node in the tree.
Dr. Nataraju A B Page - 1
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
A complete Binary Tree has all levels full of nodes, except the last level, which is can also be full, or filled from left to right. The properties of a complete Binary Tree means it is also
balanced.
A full Binary Tree is a kind of tree where each node has either 0 or 2 child nodes.
A perfect Binary Tree has all leaf nodes on the same level, which means that all levels are full of nodes, and all internal nodes have two child nodes.The properties of a perfect Binary
Tree means it is also full, balanced, and complete.
Types of Binary Tree
1. Full Binary Tree
A full Binary tree is a special type of binary tree in which every parent node/internal node has either two or no children.
Full Binary Tree
Dr. Nataraju A B Page - 2
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
2. Perfect Binary Tree
A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level.
3. Complete Binary Tree
A complete binary tree is just like a full binary tree, but with two major differences
Every level must be completely filled
All the leaf elements must lean towards the left.
The last leaf element might not have a right sibling i.e. a complete binary tree doesn't have to be a full binary tree.
binary tree representations,
struct node
Dr. Nataraju A B Page - 3
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
{
int data;
struct node *left;
struct node *right;
};
// Tree traversal in C
#include <stdio.h>
#include <stdlib.h>
struct node {
int item;
struct node* left;
struct node* right;
};
// Inorder traversal (Left, Current, Right)
void inorderTraversal(struct node* root) {
if (root == NULL)
return;
inorderTraversal(root->left);
printf("%d ->", root->item);
inorderTraversal(root->right);
}
// Preorder traversal (Current, Left, Right)
void preorderTraversal(struct node* root) {
if (root == NULL)
return;
printf("%d ->", root->item);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
Dr. Nataraju A B Page - 4
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
// Postorder traversal (Left, Right, Current)
void postorderTraversal(struct node* root) {
if (root == NULL)
return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ->", root->item);
}
// Create a new Node, Allocate memory, set data, set left and right subtree pointers to NULL
struct node* createNode(value) {
struct node* newNode = malloc(sizeof(struct node));
newNode->item = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Insert on the left of the node
struct node* insertLeft(struct node* root, int value) {
root->left = createNode(value);
return root->left;
}
// Insert on the right of the node
struct node* insertRight(struct node* root, int value) {
root->right = createNode(value);
return root->right;
}
int main() {
struct node* root = createNode(1);
insertLeft(root, 2);
insertRight(root, 3);
insertLeft(root->left, 4);
printf("Inorder traversal \n");
inorderTraversal(root);
printf("\nPreorder traversal \n");
preorderTraversal(root);
printf("\nPostorder traversal \n");
postorderTraversal(root);
}
Tree Traversal Meaning:
Tree Traversal refers to the process of visiting or accessing each node of the tree exactly once in a certain order. Tree traversal algorithms help us to visit and process all the nodes of the tree.
Since tree is not a linear data structure, there are multiple nodes which we can visit after visiting a certain node. There are multiple tree traversal techniques which decide the order in which
the nodes of the tree are to be visited.
Tree Traversal Techniques:
Dr. Nataraju A B Page - 5
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
Inorder Traversal :
Inorder traversal visits the node in the order: Left -> Root -> Right
Algorithm for Inorder Traversal:
Inorder(tree)
Traverse the left subtree, i.e., call Inorder(left->subtree)
Visit the root.
Dr. Nataraju A B Page - 6
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
Traverse the right subtree, i.e., call Inorder(right->subtree)
Uses of Inorder Traversal:
In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order.
To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal is reversed can be used.
Inorder traversal can be used to evaluate arithmetic expressions stored in expression trees.
// Given a binary tree, print its nodes in inorder
void printInorder(struct node* node)
{
if (node == NULL)
return;
// First recur on left child
printInorder(node->left);
// Then print the data of node
printf("%d ", node->data);
// Now recur on right child
printInorder(node->right);
}
Preorder Traversal :
Preorder traversal visits the node in the order: Root -> Left -> Right
Algorithm for Preorder Traversal:
Preorder(tree)
Visit the root.
Traverse the left subtree, i.e., call Preorder(left->subtree)
Dr. Nataraju A B Page - 7
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
Traverse the right subtree, i.e., call Preorder(right->subtree)
Uses of Preorder Traversal:
Preorder traversal is used to create a copy of the tree.
Preorder traversal is also used to get prefix expressions on an expression tree.
Code Snippet for Preorder Traversal:
// Given a binary tree, print its nodes in preorder
void printPreorder(struct node* node)
{
if (node == NULL)
return;
// First print data of node
printf("%d ", node->data);
// Then recur on left subtree
printPreorder(node->left);
// Now recur on right subtree
printPreorder(node->right);
}
Preorder Traversal :
Preorder traversal visits the node in the order: Root -> Left -> Right
Algorithm for Preorder Traversal:
Preorder(tree)
Visit the root.
Traverse the left subtree, i.e., call Preorder(left->subtree)
Traverse the right subtree, i.e., call Preorder(right->subtree)
Uses of Preorder Traversal:
Preorder traversal is used to create a copy of the tree.
Preorder traversal is also used to get prefix expressions on an expression tree.
Code Snippet for Preorder Traversal:
// Given a binary tree, print its nodes in preorder
void printPreorder(struct node* node)
{
if (node == NULL)
return;
// First print data of node
printf("%d ", node->data);
// Then recur on left subtree
Dr. Nataraju A B Page - 8
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
printPreorder(node->left);
// Now recur on right subtree
printPreorder(node->right);
}
Postorder Traversal :
Postorder traversal visits the node in the order: Left -> Right -> Root
Algorithm for Postorder Traversal:
Traverse the left subtree, i.e., call Postorder(left->subtree)
Traverse the right subtree, i.e., call Postorder(right->subtree)
Visit the root
Uses of Postorder Traversal:
Postorder traversal is used to delete the tree. See the question for the deletion of a tree for details.
Postorder traversal is also useful to get the postfix expression of an expression tree.
Postorder traversal can help in garbage collection algorithms, particularly in systems where manual memory management is used.
Code Snippet for Postorder Traversal:
// Given a binary tree, print its nodes according to the "bottom-up" postorder traversal.
Dr. Nataraju A B Page - 9
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
void printPostorder(struct node* node)
{
if (node == NULL)
return;
// First recur on left subtree
printPostorder(node->left);
// Then recur on right subtree
printPostorder(node->right);
// Now deal with the node
printf("%d ", node->data);
}
Huffman algorithm using Binary Tree
What is Huffman Coding?
Huffman Coding is a data compression algorithm that is used to reduce the size of data without losing any information. It achieves this by assigning shorter binary
codes to frequently occurring characters and longer codes to less frequent characters. This technique allows for efficient storage and transmission of data.
How Huffman Coding Works ?
Huffman Coding works by building a binary tree called a Huffman tree. This tree is constructed based on the frequency of occurrence of each character in the data.
The characters with higher frequencies are closer to the root of the tree, while characters with lower frequencies are placed further away.
Each leaf node of the tree represents a character, and the path from the root to the leaf node represents the binary code assigned to that character. The codes
assigned to the characters are prefix codes, meaning that no code is the prefix of another code. This property ensures that the encoded data can be uniquely
decoded.
Why Huffman Coding is Important
Huffman Coding is important in data processing and analytics for several reasons:
Data Compression: Huffman Coding allows for efficient compression of data, reducing storage space requirements and improving transmission speeds.
Information Preservation: Despite reducing the size of data, Huffman Coding ensures that no information is lost during the compression process.
Fast Decoding: The prefix codes assigned by Huffman Coding enable fast decoding of the compressed data.
Optimized Data Storage and Retrieval: Huffman Coding optimizes the storage and retrieval of data by reducing its size and improving access speeds.
Dr. Nataraju A B Page - 10
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
Important Huffman Coding Use Cases
Huffman Coding finds applications in various domains:
Data Compression: Huffman Coding is widely used in data compression algorithms such as ZIP and GZIP, reducing the size of files for storage or
transmission.
Mobile Applications: Huffman Coding is beneficial in mobile applications where limited storage and bandwidth are available.
Image and Video Compression: Huffman Coding is used in image and video compression techniques like JPEG and MPEG, enabling efficient storage and
transmission of multimedia content.
Search Engines: Huffman Coding is employed by search engines to optimize the storage and retrieval of data, improving search speeds.
Illustration of Huffman coding …
Steps to build Huffman Tree
Input is an array of unique characters along with their frequency of occurrences and output is Huffman Tree.
1. 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)
2. Extract two nodes with the minimum frequency from the min heap.
3. 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.
4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.
Let us understand the algorithm with an example:
character Frequency
a 5
b 9
c 12
d 13
e 16
f 45
Step 1. Build a min heap that contains 6 nodes where each node represents root of a tree with single node.
Step 2 Extract two minimum frequency nodes from min heap. Add a new internal node with frequency 5 + 9 = 14.
Dr. Nataraju A B Page - 11
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
Illustration of step 2
Now min heap contains 5 nodes where 4 nodes are roots of trees with single element each, and one heap node is root of tree with 3 elements
character Frequency
c 12
d 13
Internal Node 14
e 16
f 45
Step 3: Extract two minimum frequency nodes from heap. Add a new internal node with frequency 12 + 13 = 25
Dr. Nataraju A B Page - 12
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
Illustration of step 3
Now min heap contains 4 nodes where 2 nodes are roots of trees with single element each, and two heap nodes are root of tree with more than one nodes
character Frequency
Internal Node 14
e 16
Internal Node 25
f 45
Step 4: Extract two minimum frequency nodes. Add a new internal node with frequency 14 + 16 = 30
Illustration of step 4
Now min heap contains 3 nodes.
character Frequency
Internal Node 25
Internal Node 30
Dr. Nataraju A B Page - 13
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
f 45
Step 5: Extract two minimum frequency nodes. Add a new internal node with frequency 25 + 30 = 55
Illustration of step 5
Now min heap contains 2 nodes.
character Frequency
f 45
Internal Node 55
Step 6: Extract two minimum frequency nodes. Add a new internal node with frequency 45 + 55 = 100
Dr. Nataraju A B Page - 14
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
Illustration of step 6
Now min heap contains only one node.
character Frequency
Internal Node 100
Since the heap contains only one node, the algorithm stops here.
Steps to print codes from Huffman Tree:
Traverse the tree formed starting from the root. Maintain an auxiliary array. While moving to the left child, write 0 to the array. While moving to the right child, write 1 to the array. Print the
array when a leaf node is encountered.
Dr. Nataraju A B Page - 15
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
Steps to print code from HuffmanTree
The codes are as follows:
character code-word
f 0
c 100
d 101
a 1100
b 1101
e 111
The C program for Huffman coding is as follows….
#include <stdio.h>
#include <stdlib.h>
#define MAX_TREE_HT 50
Dr. Nataraju A B Page - 16
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
struct MinHNode {
char item;
unsigned freq;
struct MinHNode *left, *right;
};
struct MinHeap {
unsigned size;
unsigned capacity;
struct MinHNode **array;
};
// Create nodes
struct MinHNode *newNode(char item, unsigned freq) {
struct MinHNode *temp = (struct MinHNode *)malloc(sizeof(struct MinHNode));
temp->left = temp->right = NULL;
temp->item = item;
temp->freq = freq;
return temp;
}
// Create min heap
struct MinHeap *createMinH(unsigned capacity) {
struct MinHeap *minHeap = (struct MinHeap *)malloc(sizeof(struct MinHeap));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array = (struct MinHNode **)
malloc(minHeap->capacity * sizeof(struct MinHNode *));
return minHeap;
}
// Function to swap
void swapMinHNode(struct MinHNode **a, struct MinHNode **b) {
struct MinHNode *t = *a;
*a = *b;
*b = t;
}
// Heapify
void minHeapify(struct MinHeap *minHeap, int idx) {
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < minHeap->size
&& minHeap->array[left]->freq < minHeap->array[smallest]->freq)
smallest = left;
if (right < minHeap->size
&& minHeap->array[right]->freq < minHeap->array[smallest]->freq)
smallest = right;
if (smallest != idx) {
swapMinHNode(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
Dr. Nataraju A B Page - 17
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
}
}
// Check if size if 1
int checkSizeOne(struct MinHeap *minHeap) {
return (minHeap->size == 1);
}
// Extract min
struct MinHNode *extractMin(struct MinHeap *minHeap) {
struct MinHNode *temp = minHeap->array[0];
minHeap->array[0] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeapify(minHeap, 0);
return temp;
}
// Insertion function
void insertMinHeap(struct MinHeap *minHeap, struct MinHNode *minHeapNode) {
++minHeap->size;
int i = minHeap->size - 1;
while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {
minHeap->array[i] = minHeap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->array[i] = minHeapNode;
}
void buildMinHeap(struct MinHeap *minHeap) {
int n = minHeap->size - 1;
int i;
for (i = (n - 1) / 2; i >= 0; --i)
minHeapify(minHeap, i);
}
int isLeaf(struct MinHNode *root) {
return !(root->left) && !(root->right);
}
struct MinHeap *createAndBuildMinHeap(char item[], int freq[], int size) {
struct MinHeap *minHeap = createMinH(size);
int i;
for (i = 0; i < size; ++i)
minHeap->array[i] = newNode(item[i], freq[i]);
minHeap->size = size;
buildMinHeap(minHeap);
return minHeap;
}
struct MinHNode *buildHuffmanTree(char item[], int freq[], int size) {
struct MinHNode *left, *right, *top;
struct MinHeap *minHeap = createAndBuildMinHeap(item, freq, size);
while (!checkSizeOne(minHeap)) {
left = extractMin(minHeap);
Dr. Nataraju A B Page - 18
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
right = extractMin(minHeap);
top = newNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
insertMinHeap(minHeap, top);
}
return extractMin(minHeap);
}
void printHCodes(struct MinHNode *root, int arr[], int top) {
if (root->left) {
arr[top] = 0;
printHCodes(root->left, arr, top + 1);
}
if (root->right) {
arr[top] = 1;
printHCodes(root->right, arr, top + 1);
}
if (isLeaf(root)) {
printf(" %c | ", root->item);
printArray(arr, top);
}
}
// Wrapper function
void HuffmanCodes(char item[], int freq[], int size) {
struct MinHNode *root = buildHuffmanTree(item, freq, size);
int arr[MAX_TREE_HT], top = 0;
printHCodes(root, arr, top);
}
// Print the array
void printArray(int arr[], int n) {
int i;
for (i = 0; i < n; ++i)
printf("%d", arr[i]);
printf("\n");
}
int main() {
char arr[] = {'A', 'B', 'C', 'D'};
int freq[] = {5, 1, 6, 3};
int size = sizeof(arr) / sizeof(arr[0]);
printf(" Char | Huffman code ");
printf("\n--------------------\n");
HuffmanCodes(arr, freq, size);
}
Trees and their applications.
Dr. Nataraju A B Page - 19
Data Structures using C [BEC405D] Dept of ECE, ACIT, Bangalore
Searching – Basic searching Techniques,
Tree Searching.
Dr. Nataraju A B Page - 20
