B.Tech.

(Department of Mechanical Engineering) (III Year / V Semester)

Assignment Questions
Data Structures (U23CSTC03)

Operate pointer concept in method to insert, delete a node at a specific position in

Q.1
a Linked List.
Q.2 Summarize the next and Previous pointer in Memory address of the nodes.
Illustrate basic operations like insertion, searching, and in-order traversal in
Q.3
Binary Search Tree.
Q.4 Recommend the concept of colour of Red Black Tree.

Q.5 Summarize the structure of Binary Tree with C program.

Q.6 Evaluate different Types of Tree?

Q.7 Analyse the concept of Traversal in Binary Tree.
Q.1 Operate pointer concept in method to insert, delete a node at a specific position in a Linked
List.
Insert Elements to a Linked List
1. Insert at the beginning
Allocate memory for new node
Store data
Change next of new node to point to head
Change head to point to recently created node
struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;
newNode->next = head;
head = newNode;
2. Insert at the End
Allocate memory for new node
Store data
Traverse to last node
Change next of last node to recently created node
struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;
newNode->next = NULL;

struct node *temp = head;

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

temp->next = newNode;
3. Insert at the Middle
Allocate memory and store data for new node
Traverse to node just before the required position of new node
Change next pointers to include new node in between
struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;

struct node *temp = head;

for(int i=2; i < position; i++) {

if(temp->next != NULL) {
temp = temp->next;
}
}
newNode->next = temp->next;
temp->next = newNode;
Delete from a Linked List
You can delete either from the beginning, end or from a particular position.

1. Delete from beginning

Point head to the second node
head = head->next;
2. Delete from end
Traverse to second last element
Change its next pointer to null
struct node* temp = head;
while(temp->next->next!=NULL){
temp = temp->next;
}
temp->next = NULL;
3. Delete from middle
Traverse to element before the element to be deleted
Change next pointers to exclude the node from the chain
for(int i=2; i< position; i++) {
if(temp->next!=NULL) {
temp = temp->next;
}
}

temp->next = temp->next->next;

Q.2 Summarize the next and Previous pointer in Memory address of the nodes.
Memory Representation of a Linked List
Unlike arrays, where elements are stored in contiguous memory locations, linked lists
allocate memory dynamically for each node. This means that each node can be located
anywhere in the memory and they are connected via pointers.

Before looking at the memory representation of singly linked list. Let's first create a linked
list having four nodes. Each node has two parts: one part holds a value (data) and the other
part holds the address of the next node. The first node is called the head node and it points to
the first element in the list. The last node in the list points to NULL, which means there are
no more nodes after it.
In the above singly linked list, each node is connected by pointers. These pointers show the
address of the next node, which allowing us to move through the list in forward direction.
This connection is shown with arrows in the diagram, making it clear how each node links to
the next one.

How is Memory Allocation done for Linked List?

Let's see how memory is allocated for the linked list. The images below illustrate this more
clearly.

Memory-allocation-of-Linked-List
Let's see how memory is allocated for the linked list. The images below illustrate this more
clearly.

Heap Memory: The nodes of the linked list are dynamically allocated, which allocate
memory from the heap. Heap memory is used for objects whose size may not be known at
compile time and allows for dynamic memory management.
Stack Memory: The pointer "head" is typically defined within a function (like main). Local
variables, including pointers, are stored in the stack, which has a fixed size and is managed
automatically when the function is called and returns.

Q.3 Illustrate basic operations like insertion, searching, and in-order traversal in
Binary Search Tree.

Operation on BST:

1. Insertion

Say we have to build a BST of the keys, 50, 80, 30, 20, 100, 40. It can be clearly
seen below, for inserting, first the key is compared is compared with the root, if
smaller then go to Left subtree else Right subtree. The same step is repeated until
all the keys are inserted.

Insertio
n to BST

2. Searching

The steps follow in the insertion, are same followed here. Only difference is in
comparison, if the key is not matched, repeat the steps till reached NULL. That says,
desired key is not available in the BST.

Searc
hing key in a BST

3.In-order Traversal in a Binary Search Tree (BST)

In-order traversal is a depth-first traversal technique where nodes are

visited in the following sequence:

1. Left Subtree: Visit all nodes in the left subtree.

 2. Root Node: Process the root node.
3. Right Subtree: Visit all nodes in the right subtree.

For a Binary Search Tree (BST), in-order traversal is particularly useful

because it visits the nodes in ascending sorted order.

Algorithm (Recursive Approach)

1. Traverse the left subtree by recursively calling the in-order function.

2. Visit the root node (process or print its value).
3. Traverse the right subtree by recursively calling the in-order
function.

Q.4 Recommend the concept of colour of Red Black Tree.

What is a Red-Black Tree?

A Red-Black Tree is a self-balancing binary search tree where each node has an additional
attribute: a color, which can be either red or black. The primary objective of these trees is to
maintain balance during insertions and deletions, ensuring efficient data retrieval and
manipulation.

Properties of Red-Black Trees

A Red-Black Tree have the following properties:

Node Color: Each node is either red or black.

Root Property: The root of the tree is always black.

Red Property: Red nodes cannot have red children (no two consecutive red nodes on any
path).

Black Property: Every path from a node to its descendant null nodes (leaves) has the same
number of black nodes.

Leaf Property: All leaves (NIL nodes) are black.

These properties ensure that the longest path from the root to any leaf is no more than twice
as long as the shortest path, maintaining the tree's balance and efficient performance.

Example of Red-Black Tree:

New-Project-8

The Correct Red-Black Tree in above image ensures that every path from the root to a leaf
node has the same number of black nodes. In this case, there is one (excluding the root node).

The Incorrect Red Black Tree does not follow the red-black properties as two red nodes are
adjacent to each other. Another problem is that one of the paths to a leaf node has zero black
nodes, whereas the other two contain a black node.

Why Red-Black Trees?

Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where
h is the height of the BST. The cost of these operations may become O(n) for a skewed
Binary tree. If we make sure that the height of the tree remains O(log n) after every insertion
and deletion, then we can guarantee an upper bound of O(log n) for all these operations. The
height of a Red-Black tree is always O(log n) where n is the number of nodes in the tree.

Sr. No. Algorithm Time Complexity

1. Search O(log n)

2. Insert O(log n)

3. Delete O(log n)

Comparison with AVL Tree:

The AVL trees are more balanced compared to Red-Black Trees, but they may cause more
rotations during insertion and deletion. So if your application involves frequent insertions and
deletions, then Red-Black trees should be preferred. And if the insertions and deletions are
less frequent and search is a more frequent operation, then AVL tree should be preferred over
the Red-Black Tree.

How does a Red-Black Tree ensure balance?

A simple example to understand balancing is, that a chain of 3 nodes is not possible in the
Red-Black tree. We can try any combination of colors and see if all of them violate the Red-
Black tree property.

Q.5 Summarize the structure of Binary Tree with C program.

Binary Tree Structure and C Program

A binary tree is a hierarchical data structure where each node has at most two children,
referred to as the left child and right child. It is widely used in applications like searching,
sorting, and hierarchical data representation.

Key Features of Binary Tree

1. Node Structure:
o Each node contains:
 A data value.
 A pointer to the left child.
 A pointer to the right child.
2. Types of Binary Trees:
o Full Binary Tree: Every node has 0 or 2 children.
o Complete Binary Tree: All levels are completely filled except possibly the
last, which is filled from left to right.
o Perfect Binary Tree: All internal nodes have two children, and all leaves are at
the same level.
3. Basic Operations:
o Insertion
o Deletion
o Traversals (Inorder, Preorder, Postorder)
C Program Example for Binary Tree

Copy code#include <stdio.h>

#include <stdlib.h>
// Define the structure of a node
struct Node {
int data;
struct Node* left;
struct Node* right;
};

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Inorder Traversal (Left, Root, Right)

void inorderTraversal(struct Node* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}

// Main function
int main() {
// Create the root node
 struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);

printf("Inorder Traversal: ");

inorderTraversal(root);
return 0;
}

Explanation of the Program

1. Node Creation:
o The createNode function dynamically allocates memory for a new node and
initializes its data and child pointers.
2. Tree Construction:
o A simple binary tree is constructed manually by linking nodes.
3. Traversal:
o The inorderTraversal function recursively visits the left subtree, processes the
root, and then visits the right subtree.

This program demonstrates the basic structure and traversal of a binary tree in C. You can
extend it to include other operations like insertion, deletion, or additional traversal methods.

Q.6 Evaluate different Types of Tree?

The main types of trees in data structure are:

1. Binary Tree

A binary tree is a tree data structure where each node has at most two children. These two
children are usually referred to as the left child and right child. It is widely used in
applications such as binary search trees and heaps.

Example: Consider the tree below. Since each node of this tree has only 2 children, it can be
said that this tree is a Binary Tree
Binary Tree
Examples / Types of Binary Tree:
 Complete Binary Tree: A binary tree in which every level, except possibly the
last, is completely filled, and all nodes are as far left as possible. For example,
a heap is a complete binary tree that satisfies the heap property (either max-heap
or min-heap).
 Full Binary Tree: A binary tree where every node has either 0 or 2 children.
 Degenerate Binary Tree (or Pathological Tree): A tree in which each parent
node has only one child. This essentially forms a linked list, which leads to
inefficient operations.
 Binary Search Tree (BST) and its Variations: A BST is a binary tree where
each node has at most two children, and for each node, the left child’s value is
smaller than the node’s value, and the right child’s value is greater. An AVL
Tree is a self-balancing BST where the heights of the two child subtrees of any
node differ by no more than one. Red Black Tree and Splay Tree are more
example variations of BST.
 Binary Indexed Tree (Fenwick Tree): A data structure that uses a binary tree
to efficiently compute and update prefix sums in an array.
 Perfect Binary Tree: A binary tree where all internal nodes have two children
and all leaf nodes are at the same level.
 Balanced Binary Tree: A binary tree where the difference in heights between
the left and right subtrees of any node is minimal (often defined as at most 1).
Examples of Balanced Binary Tree are AVL Tree, Red Black Tree and Splay
Tree
 Segment Tree: A segment tree is a binary tree used for storing intervals or
segments. It allows efficient querying and updating of ranges of values, making
it particularly useful for problems that involve finding the sum, minimum,
maximum, or other operations over a range of elements in an array.
 To know more about the types of the binary trees, please refer to this detailed article:
Types of Binary Tree .
2. Ternary Tree
A Ternary Tree is a tree data structure in which each node has at most three child nodes,
usually distinguished as “left”, “mid” and “right”.
Example: Consider the tree below. Since each node of this tree has only 3 children, it can
be said that this tree is a Ternary Tree.

Examples of Ternary Tree:

 Ternary Search Tree: A ternary search tree is a special trie data structure
where the child nodes of a standard trie are ordered as a binary search tree.
 Ternary Heap: A type of heap where each node can have up to three children,
though less common than binary heaps.
3. N-ary Tree (Generic Tree)
Generic trees are a collection of nodes where each node is a data structure that consists of
records and a list of references to its children(duplicate references are not allowed).
Unlike the linked list, each node stores the address of multiple nodes.
Every node stores the addresses of its children and the very first node’s address will be
stored in a separate pointer called root.
1. Many children at every node.
2. The number of nodes for each node is not known in advance.
Example:

N-ary Tree
Examples of N-ary Trees:
 B-tree: A self-balancing search tree where nodes can have multiple children,
usually used for indexing large databases.
 B+ Tree: A B+ tree is a variation of the B-tree that only stores data in the leaf
nodes, making range queries more efficient.
  Trie (Prefix Tree): A tree where each node represents a character, and paths
from the root to leaves represent strings. It can have a variable number of
children for each node, making it an N-ary tree.

Q.7 Analyse the concept of Traversal in Binary Tree.

Given a binary tree, the task is to print all the nodes of the binary tree in Pre-order, Post-
order, and In-order in one iteration.
Examples:
Input:

Output:
Pre Order: 1 2 4 5 3 6 7
Post Order: 4 5 2 6 7 3 1
In Order: 4 2 5 1 6 3 7
Input:

Output:
Pre Order: 1 2 4 8 12 5 9 3 6 7 10 11
Post Order: 12 8 4 9 5 2 6 10 11 7 3 1
In Order: 8 12 4 2 9 5 1 6 3 10 7 11

Copy code

void inOrder(struct Node* root) {

if (root != NULL) {

inOrder(root->left);

printf("%d ", root->data);

inOrder(root->right);

Pre-order Traversal (Root, Left, Right):

Visits the root node first, then the left subtree, and finally the right subtree.
Useful for creating a copy of the tree or prefix expressions.

Copy code

void preOrder(struct Node* root) {

if (root != NULL) {

printf("%d ", root->data);

preOrder(root->left);

preOrder(root->right);

Post-order Traversal (Left, Right, Root):

Visits the left subtree first, then the right subtree, and finally the root node.

Useful for deleting the tree or evaluating postfix expressions.

Copy code

void postOrder(struct Node* root) {

if (root != NULL) {

postOrder(root->left);

postOrder(root->right);

printf("%d ", root->data);

Level-order Traversal (Breadth-First):

Visits nodes level by level from top to bottom.

Implemented using a queue.

Copy code

void levelOrder(struct Node* root) {

if (root == NULL) return;

struct Queue* q = createQueue();

enqueue(q, root);

while (!isEmpty(q)) {
 struct Node* current = dequeue(q);

printf("%d ", current->data);

if (current->left != NULL) enqueue(q, current->left);

if (current->right != NULL) enqueue(q, current->right);

}
 Q.1 Evaluate pointer concept of Linked list?

Initialize three pointers:

Current pointer (curr): Points to the current node.

Previous pointer (prev): Points to the previous node.

Next pointer (next): Points to the next node.

Q.2 Differentiate in-order, pre-order and post order traversal in binary tree.

In-order traversal first visits the left subtree, then the root node, and finally the right subtree.

Pre-order traversal visits the root node first, then the left subtree, and finally the right subtree.

Post-order traversal visits the left subtree first, then the right subtree, and finally the root node.

Q.3 Compare single Threaded and Double Threaded Tree.

double-threaded binary tree

In a single-threaded binary tree, only the right NULL pointer is pointed to in order successor.

In a double-threaded binary tree, both the right and left NULL pointers are pointed to in order successor and
predecessor respectively.

Q.4 List out the basic components of Tree.

Basic Components of a Tree in Data Structure

Root: The topmost node in a tree. It serves as the starting point, and every tree has exactly one root node.

Node: Each element in the tree is called a node. A node contains data and may have child nodes.

Edge: A connection between two nodes. It represents the relationship between parent and child nodes.

Parent: A node that has one or more child nodes connected to it.

Child: A node that is directly connected to another node (its parent) above it.

Leaf: A node that has no children. These are the terminal nodes of the tree.

Subtree: A portion of the tree that consists of a node and all its descendants.

Height: The length of the longest path from the root to a leaf node.

Depth: The number of edges from the root to a specific node.

Level: The depth of a node, starting from the root at level 0.

Degree: The number of children a node has.

Q.5 Determine Balance Factor in AVL Tree?

An AVL Tree is a self-balancing Binary Search Tree (BST) where the difference in heights between the left and
right sub-trees (called the Balance Factor) of any node is at most 1.

It is named after its inventors Adelson-Velsky and Landis.

Balance factor = Height of left sub tree - Height of right sub tree

Valid balance factors: –1, 0, +1