ATRIA INSTITUTE OF TECHNOLOGY

Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

Assignment- II

Subject: Data Structures and Applications Sem: III Subject code: BCS304

[Link] is singly linked list. Write a C function for following operations on

singly linked list CO3

i) Insertion at beginning
ii) Insertion at end
iii) Deletion at the beginning
iv) Deletion at end
A singly linked list is a type of data structure that consists of nodes, where
each node contains:
 Data: The actual information stored in the node.
 Pointer: A pointer to the next node in the list.
In a singly linked list, nodes are connected in a single direction. The last node
in the list points to NULL, indicating the end of the list.

C Functions for Operations on a Singly Linked List

Here’s how you can implement the basic operations on a singly linked list in
C, including:
1. Insertion at the beginning
2. Insertion at the end
3. Deletion at the beginning
4. Deletion at the end
c
Copy code
#include <stdio.h>
#include <stdlib.h>

// Define the singly linked list node structure

struct Node {
int data;
struct Node* next;
};

// Function to insert a node at the beginning of the list

void insertAtBeginning(struct Node** head_ref, int new_data) {
// Allocate memory for the new node and add data
struct Node* new_node = (struct Node*)malloc(sizeof(struct
Node));
new_node->data = new_data;

// Make the new node point to the current head

new_node->next = *head_ref;

// Move the head to point to the new node

*head_ref = new_node;
}

// Function to insert a node at the end of the list

void insertAtEnd(struct Node** head_ref, int new_data) {
// Allocate memory for the new node and add data
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

struct Node* new_node = (struct Node*)malloc(sizeof(struct

Node));
new_node->data = new_data;
new_node->next = NULL;

// If the list is empty, make the new node the head

if (*head_ref == NULL) {
*head_ref = new_node;
return;
}

// Traverse to the last node

struct Node* last = *head_ref;
while (last->next != NULL)
last = last->next;

// Make the last node point to the new node

last->next = new_node;
}

// Function to delete a node from the beginning of the list

void deleteAtBeginning(struct Node** head_ref) {
if (*head_ref == NULL) {
printf("The list is empty.\n");
return;
}

// Store the current head and move the head pointer to the
next node
struct Node* temp = *head_ref;
*head_ref = (*head_ref)->next;

// Free the memory of the original head

free(temp);
}

// Function to delete a node from the end of the list

void deleteAtEnd(struct Node** head_ref) {
if (*head_ref == NULL) {
printf("The list is empty.\n");
return;
}

struct Node* temp = *head_ref;

// If there's only one node in the list

if (temp->next == NULL) {
*head_ref = NULL;
free(temp);
return;
}

// Traverse to the second-last node

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

// Free the last node and set the second-last node's next
to NULL
free(temp->next);
temp->next = NULL;
}
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

// Utility function to print the linked list

void printList(struct Node* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}

// Main function to demonstrate the operations

int main() {
struct Node* head = NULL;

insertAtBeginning(&head, 1);
insertAtBeginning(&head, 2);
insertAtEnd(&head, 3);
insertAtEnd(&head, 4);

printf("Linked list after insertions: ");

printList(head);

deleteAtBeginning(&head);
printf("Linked list after deletion at the beginning: ");
printList(head);

deleteAtEnd(&head);
printf("Linked list after deletion at the end: ");
printList(head);

return 0;
}

Explanation of Each Operation

1. Insertion at the Beginning (insertAtBeginning):
o A new node is created and data is assigned to it.
o The new node’s next pointer is set to the current head.
o The head pointer is updated to point to the new node.
2. Insertion at the End (insertAtEnd):
o A new node is created with the provided data, and its next pointer
is set to NULL.
o If the list is empty, the new node becomes the head.
o Otherwise, we traverse to the end of the list and update the last
node’s next pointer to point to the new node.
3. Deletion at the Beginning (deleteAtBeginning):
o If the list is empty, a message is displayed.
o Otherwise, we store the current head in a temporary variable and
move the head pointer to the next node.
o The original head node is then freed to release the memory.
4. Deletion at the End (deleteAtEnd):
o If the list is empty, a message is displayed.
o If there is only one node, we delete it and set the head to NULL.
o Otherwise, we traverse to the second-to-last node, free the last
node, and set the second-to-last node’s next pointer to NULL.
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

2. For the given sparse matrix, give the linked list representation with CO3
necessary C declarations.

3. Write a node structure for linked representation of a polynomial . Write C CO3

function to add two polynomials. show the linked list representation of below
two polynomial and in addition
POLY1:5x2+4x+2
POLY2:3x2+2x+5
4. Discuss how to implement stacks Singly using linked list. Write C function CO3
and structure for it. 1. add to a linked list (push) 2. delete from linked list
(pop)
[Link] is the advantage of doubly linked list over singly linked list? Illustrate CO3
with an example.

A doubly linked list offers several advantages over a singly linked list
because each node contains two pointers: one pointing to the next node and
another pointing to the previous node. This additional pointer enables certain
operations to be more efficient and flexible in a doubly linked list.

Advantages of Doubly Linked List over Singly Linked List

1. Bidirectional Traversal:
o In a singly linked list, you can only traverse the list in one direction
(from head to tail).
o In a doubly linked list, you can traverse the list in both directions
(from head to tail and from tail to head), which makes it easier to go
backward when needed.
2. Easier Deletion of a Node:
o In a singly linked list, to delete a node, you need a pointer to the
previous node, which often requires traversing the list from the
beginning to find it.
o In a doubly linked list, each node has a pointer to its previous node,
so you can delete a node directly without needing to know the
previous node, making deletion easier and faster.
3. Easier Insertion at the End:
o In a singly linked list, to insert at the end, you must traverse the
entire list to reach the last node.
o In a doubly linked list, if you maintain a pointer to the last node,
insertion at the end becomes a constant-time operation since you
have both the head and tail pointers.
4. Better for Implementing Certain Data Structures:
o Certain data structures, like deques (double-ended queues), are
easier and more efficient to implement with a doubly linked list since
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

both ends of the list can be accessed and modified efficiently.

[Link] a linked list and create basic C functions to perform following CO3
operation on SLL:
i. Combine two linked lists.
ii. Reverse a linked list.
iii. count number of nodes/length of the SLL
iv. Search for a node
7. Define a linked list and create basic C functions to perform following CO3
operation on SLL:
i. Combine two linked lists.
ii. Reverse a linked list.
iii. count number of nodes/length of the SLL
iv. Search for a node

Linked Lists and Operations

A linked list is a linear data structure composed of individual elements called
nodes, where each node stores data and a pointer (or reference) to the next
node in the sequence12. Unlike arrays, linked lists do not require contiguous
memory allocation, offering flexibility in memory management and efficient
insertion and deletion operations.
Types of Linked Lists:
●
Singly Linked List (SLL): Each node points only to the next node in the
sequence2.
●
Doubly Linked List (DLL): Each node has two pointers, one to the next node
and one to the previous node3.
●
Circular Linked List: The last node points back to the first node, creating a
circular structure45.
Basic C Functions for SLL Operations:
i. Combining Two Linked Lists:
This operation involves appending the second linked list to the end of the first
linked list. The sources provide a function for concatenating two singly linked
lists:
listpointer concatenate(listpointer ptr1, listpointer ptr2) {
if (!ptr1) return ptr2; // If the first list is empty, return
the second list
if (!ptr2) return ptr1; // If the second list is empty,
return the first list

listpointer temp = ptr1;

while (temp->link != NULL) { // Traverse to the end of the
first list
temp = temp->link;
}
temp->link = ptr2; // Link the end of the first list to the
start of the second list
return ptr1;
}
Explanation:
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

1.
Empty List Check: The function first checks if either of the input lists is
empty. If so, it returns the other list.
2.
Find End of First List: It then traverses the first list using a temporary pointer
(temp) until it reaches the last node (where temp->link is NULL).
3.
Connect Lists: The link field of the last node of the first list is set to point to
the head of the second list, effectively combining the two lists.
4.
Return Head: The function returns the head of the combined list (which is the
head of the first list).
ii. Reversing a Linked List
Reversing a linked list involves changing the direction of the pointers so that
the last node becomes the head and the previous head becomes the tail.
Source6 provides a function to invert a singly linked list:
listpointer invert(listpointer lead) {
listpointer middle, trail;
middle = NULL;
while (lead != NULL) {
trail = middle;
middle = lead;
lead = lead->link;
middle->link = trail;
}
return middle;
}
Explanation:
1.
Initialization: middle and trail pointers are initialized to NULL. middle
will keep track of the reversed list's head.
2.
Iteration: The while loop iterates through the original list. In each step:
○
trail is set to the previous middle.
○
middle is set to the current node (lead).
○
lead is advanced to the next node.
○
The link of the current middle node is set to trail, effectively reversing
the link direction.
3.
Return New Head: After the loop, middle points to the new head of the
reversed list.
iii. Counting Nodes/Length of the SLL
This operation involves traversing the linked list and incrementing a counter
for each node encountered. The sources do not explicitly provide a function for
this, but it can be easily implemented:
int countNodes(NODE first) {
int count = 0;
NODE cur = first;
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

while (cur != NULL) {

count++;
cur = cur->link;
}
return count;
}
Explanation:
1.
Initialization: A counter variable count is initialized to 0, and a temporary
pointer cur is set to the head of the list.
2.
Traversal and Counting: The while loop iterates through the list. In each
iteration, the counter is incremented, and the cur pointer is moved to the next
node.
3.
Return Count: After the loop, the count variable holds the total number of
nodes, which is returned.
iv. Searching for a Node
This operation involves traversing the linked list and comparing the data in
each node with the target value. The sources do not provide a function for
searching in an SLL but here's an implementation:
NODE searchNode(NODE first, int key) {
NODE cur = first;
while (cur != NULL) {
if (cur->data == key) {
return cur;
}
cur = cur->link;
}
return NULL;
}
Explanation:
1.
Initialization: A temporary pointer cur is set to the head of the list.
2.
Traversal and Comparison: The while loop iterates through the list. In
each iteration, the data in the current node is compared with the key. If they
match, the node is returned.
3.
Node Not Found: If the loop completes without finding the key, NULL is
returned to indicate that the node is not present in the list.

8. Define the structure of a node in a doubly linked list and implement C CO3
functions for inserting and deleting nodes within a circular doubly linked list.

9. Define binary trees and elaborate on the memory representation of a binary CO4
tree with an example

A binary tree is a hierarchical data structure in which each node has at most
two children, typically referred to as the left child and right child. Binary
trees are widely used in computer science for applications such as organizing
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

data hierarchically, implementing efficient search and retrieval algorithms, and

facilitating operations in graphics, AI, and database indexing.

Key Properties of a Binary Tree

1. Node: Each node contains data and references (or pointers) to its children.
2. Root: The topmost node of the binary tree is called the root.
3. Child Nodes: Each node can have a left child, right child, or both.
4. Leaf Node: A node with no children is called a leaf node.
5. Internal Node: A node with at least one child.
6. Subtree: A portion of a tree itself is a tree rooted at one of its nodes.

Types of Binary Trees

 Full Binary Tree: Each node has either 0 or 2 children.
 Perfect Binary Tree: All internal nodes have two children, and all leaves are
at the same level.
 Complete Binary Tree: All levels are completely filled except possibly the
last, which is filled from the left.
 Binary Search Tree (BST): A binary tree in which the left child of a node has a
smaller value, and the right child has a greater value.

Memory Representation of a Binary Tree

Binary trees can be represented in memory using linked representation and
array-based representation.

1. Linked Representation
In the linked representation, each node in the binary tree is implemented as a
structure (or class) with:
 A data field to hold the node's value.
 A pointer to the left child.
 A pointer to the right child.

Example of Linked Representation in C

To illustrate, let’s construct a simple binary tree:
mathematica
Copy code
A
/ \
B C
/ \
D E
Each node is represented as a structure with fields for data, left, and right
pointers.
c
Copy code
#include <stdio.h>
#include <stdlib.h>

// Define the structure of a binary tree node

struct Node {
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

char data;
struct Node* left;
struct Node* right;
};

// Function to create a new node

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

int main() {
// Manually create the tree nodes
struct Node* root = createNode('A');
root->left = createNode('B');
root->right = createNode('C');
root->left->left = createNode('D');
root->left->right = createNode('E');

// Print structure (just to verify)

printf("Root Node: %c\n", root->data);
printf("Left Child of Root: %c\n", root->left->data);
printf("Right Child of Root: %c\n", root->right->data);
printf("Left Child of Node B: %c\n", root->left->left-
>data);
printf("Right Child of Node B: %c\n", root->left->right-
>data);

return 0;
}
In this representation:
 Each node points to its left and right children.
 The createNode function allocates memory for a new node, sets its data,
and initializes its left and right pointers to NULL.

Memory Layout in Linked Representation

Each node is stored separately in memory, connected via pointers:
 Node A has pointers to nodes B and C.
 Node B has pointers to nodes D and E.

[Link] is tree? With suitable example, define CO4

i. Height /depth of a tree
ii. complete binary tree
iii. fully binary tree
iv. degree of a node

Defining Trees and Their Properties

A tree is a hierarchical data structure consisting of nodes connected by edges,
representing a parent-child relationship between the nodes. It is a non-linear
data structure, unlike arrays or linked lists, where data is organized
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

sequentially.1
●
Each tree has a special node called the root, which has no parent.2 All other
nodes in the tree are descendants of the root, forming subtrees.2
●
The edges connect the nodes, representing the parent-child relationship.3
●
Nodes with the same parent are called siblings.4
●
Nodes with no children are called leaf nodes or terminal nodes.5
●
Nodes with at least one child are called internal nodes or non-terminal
nodes.6
Example Tree7
A
/ \
B C
/ \ \
D E F
i. Height/Depth of a Tree:
●
Height of a Node: The number of edges in the longest path from a node to a
leaf node.8
●
Height of a Tree: The height of the root node, which is the length of the
longest path from the root to a leaf node.8
●
Depth of a Node: The number of edges in the path from the root node to that
node.8
●
Depth of a Tree: The depth of the deepest leaf node, which is the length of the
longest path from the root to a leaf node.8
In the example tree above:
●
Height of node B is 2.
●
Height of the tree (height of node A) is 3.
●
Depth of node E is 2.
●
Depth of the tree is 3.
ii. Complete Binary Tree:
A complete binary tree is a binary tree in which:
●
All levels are completely filled, except possibly the last level.9
●
The nodes in the last level are as far left as possible.9
Examples of complete binary trees:10
A A A
/ \ / \ /
B C B C B
/ \ \ / \ / \
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

D E F D E D E
iii. Fully Binary Tree (Strictly Binary Tree):
A fully binary tree (also known as a strictly binary tree) is a binary tree in
which every node other than the leaf nodes has exactly two children.11
Example of a fully binary tree:11
A
/ \
B C
/ \ / \
D E F G
iv. Degree of a Node:
The degree of a node in a tree is the total number of children that node has.612
In the example tree:
●
Degree of node A is 2.
●
Degree of node B is 2.
●
Degree of node D is 0 (leaf node).
The highest degree of a node among all the nodes in a tree is called the degree
of the tree.6 In the example tree, the degree of the tree is 2

[Link] the below given tree, using CO3

i) Linked list representation
ii) Left child right sibling representation.

12. Define binary tree. List the properties of binary tree and discuss the types CO4
of binary trees.
13. Write C recursive routine to traverse the binary tree using inorder, CO4
preorder and postorder

To traverse a binary tree in different orders (inorder, preorder, and postorder),

we can use recursive functions in C. Each traversal method visits the nodes in
a different order:
1. Inorder Traversal: Left subtree → Root → Right subtree
2. Preorder Traversal: Root → Left subtree → Right subtree
3. Postorder Traversal: Left subtree → Right subtree → Root
Here is a C program that defines a binary tree structure and includes recursive
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

functions for each traversal method.

c
Copy code
#include <stdio.h>
#include <stdlib.h>

// Define the structure of a tree 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 inorder(struct Node* node) {
if (node == NULL)
return;

inorder(node->left);
printf("%d ", node->data);
inorder(node->right);
}

// Preorder Traversal (Root, Left, Right)

void preorder(struct Node* node) {
if (node == NULL)
return;

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

preorder(node->left);
preorder(node->right);
}

// Postorder Traversal (Left, Right, Root)

void postorder(struct Node* node) {
if (node == NULL)
return;

postorder(node->left);
postorder(node->right);
printf("%d ", node->data);
}

// Main function to demonstrate the traversal

int main() {
// Manually creating a binary tree for demonstration
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

root->right->left = createNode(6);
root->right->right = createNode(7);

printf("Inorder traversal: ");

inorder(root);
printf("\n");

printf("Preorder traversal: ");

preorder(root);
printf("\n");

printf("Postorder traversal: ");

postorder(root);
printf("\n");

return 0;
}

Explanation of the Code

1. Data Structure:
o struct Node defines a binary tree node with an integer data and
pointers to its left and right children.
2. Create Node Function:
o createNode(int data) creates a new node with the given data
and initializes the left and right children as NULL.
3. Traversal Functions:
o Inorder Traversal (inorder): First recursively visits the left subtree,
then the root node, and finally the right subtree.
o Preorder Traversal (preorder): First processes the root node, then
recursively visits the left subtree, and finally the right subtree.
o Postorder Traversal (postorder): First recursively visits the left
subtree, then the right subtree, and finally processes the root node.
4. Main Function:
o Constructs a simple binary tree manually for demonstration
purposes.
o Calls each traversal function and prints the nodes in the specified
order.

14. Given the following traversal, Draw a binary tree for the following: CO4

i) Inorder sequence - 8,4,10,9,11,2,5,1,6,3,7 and

Preorder sequence - 1,2,4,8,9,10,11,5,3,6,7.

ii) Post order : 9, 1, 2, 12, 7, 5, 3, 11, 4, 8 and

Inorder: 9, 5, 1, 7, 2, 12, 8, 4, 3, 11

To construct a binary tree from given traversal sequences, we’ll use the
properties of inorder, preorder, and postorder traversals.

Problem (i):
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

 Inorder sequence: 8, 4, 10, 9, 11, 2, 5, 1, 6, 3, 7

 Preorder sequence: 1, 2, 4, 8, 9, 10, 11, 5, 3, 6, 7

Steps:
1. In a preorder traversal, the first element is the root of the tree or subtree.
2. Using the inorder sequence, we can find the elements in the left and right
subtrees by locating the root in the inorder sequence.
3. We recursively apply the same steps for each subtree.

Solution:
1. From the preorder sequence, the first element is 1, which is the root
of the tree.
2. Find 1 in the inorder sequence. Everything to the left of 1 (8, 4, 10,
9, 11, 2, 5) belongs to the left subtree, and everything to the right
of 1 (6, 3, 7) belongs to the right subtree.
3. For the left subtree:
o The next element in the preorder sequence is 2, which is the root of
the left subtree.
o Find 2 in the inorder sequence (8, 4, 10, 9, 11, 2, 5), where
the left part (8, 4, 10, 9, 11) is the left subtree of 2, and the
right part (5) is the right subtree of 2.
4. For the right subtree of 1:
o The next element in the preorder sequence after processing the left
subtree is 3, which is the root of the right subtree.
o Find 3 in the inorder sequence (6, 3, 7), where 6 is the left child
of 3 and 7 is the right child of 3.
5. We continue this process recursively until the entire tree is constructed.
Following these steps, the binary tree for Problem (i) would look like this:
markdown
Copy code
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
/ \
10 11

Problem (ii):
 Postorder sequence: 9, 1, 2, 12, 7, 5, 3, 11, 4, 8
 Inorder sequence: 9, 5, 1, 7, 2, 12, 8, 4, 3, 11

Steps:
1. In a postorder traversal, the last element is the root of the tree or subtree.
2. Using the inorder sequence, we can find the elements in the left and right
subtrees by locating the root in the inorder sequence.
3. We recursively apply the same steps for each subtree.
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

Solution:
1. From the postorder sequence, the last element is 8, which is the root
of the tree.
2. Find 8 in the inorder sequence. Everything to the left of 8 (9, 5, 1,
7, 2, 12) belongs to the left subtree, and everything to the right of 8
(4, 3, 11) belongs to the right subtree.
3. For the left subtree:
o The last element in the left part of the postorder sequence before 8
is 2, which is the root of the left subtree.
o Find 2 in the inorder sequence (9, 5, 1, 7, 2, 12), where the
left part (9, 5, 1, 7) is the left subtree of 2, and the right part
(12) is the right subtree of 2.
4. For the right subtree of 8:
o The next element in the postorder sequence before 2 is 4, which is
the root of the right subtree.
o Find 4 in the inorder sequence (4, 3, 11), where 3 is the left child
of 4 and 11 is the right child of 4.
5. We continue this process recursively until the entire tree is constructed.
Following these steps, the binary tree for Problem (ii) would look like this:
markdown
Copy code
8
/ \
2 4
/ \ / \
1 12 3 11
/ \
5 7
/
9

[Link] the following CO4

i−1
[Link] maximum number of nodes on level i of a binary tree is 2 & The
maximum number of nodes in a binary tree of depth k is 2k −1 ,k > 1
2. For any nonempty binary tree, T, if n 0 is the number of leaf nodes and n2 the
number of nodes of degree 2, then n 0=n2 +1

1. Maximum Number of Nodes at Level iii and Maximum Number

of Nodes in a Binary Tree of Depth kkk
Statement 1:
 The maximum number of nodes on level iii of a binary tree is 2i−12^{i -
1}2i−1.
 The maximum number of nodes in a binary tree of depth kkk is 2k−12^k -
12k−1, where k>1k > 1k>1.
Proof:

Part (a): Maximum Number of Nodes on Level iii

ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

In a binary tree:
 The root is considered level 1.
 At each level, each node can have at most two children.
Thus:
 Level 1 (the root) has a maximum of 21−1=20=12^{1 - 1} = 2^0 =
121−1=20=1 node.
 Level 2 can have a maximum of 22−1=21=22^{2 - 1} = 2^1 = 222−1=21=2
nodes.
 Level 3 can have a maximum of 23−1=22=42^{3 - 1} = 2^2 = 423−1=22=4
nodes.
 And so on.
In general, level iii can have at most 2i−12^{i - 1}2i−1 nodes. This is because
each node in a binary tree can have up to two children, and as you go down
each level, the maximum number of nodes doubles.

Part (b): Maximum Number of Nodes in a Binary Tree of Depth kkk

A binary tree of depth kkk is a tree with kkk levels (from level 1 to level kkk).
If each level has the maximum number of nodes (i.e., the tree is a full binary
tree), then:
 Level 1 has 21−1=20=12^{1 - 1} = 2^0 = 121−1=20=1 node.
 Level 2 has 22−1=21=22^{2 - 1} = 2^1 = 222−1=21=2 nodes.
 Level 3 has 23−1=22=42^{3 - 1} = 2^2 = 423−1=22=4 nodes.
 ...
 Level kkk has 2k−12^{k - 1}2k−1 nodes.
The total maximum number of nodes in the tree is the sum of the nodes at all
levels from 1 to kkk:
Total nodes=20+21+22+⋯+2k−1\text{Total nodes} = 2^0 + 2^1 + 2^2 + \cdots + 2^{k
- 1}Total nodes=20+21+22+⋯+2k−1
This is a geometric series with kkk terms, where the sum is:
Total nodes=2k−1\text{Total nodes} = 2^k - 1Total nodes=2k−1
Thus, the maximum number of nodes in a binary tree of depth kkk is 2k−12^k
- 12k−1.

2. For Any Nonempty Binary Tree TTT: If n0n_0n0 is the Number

of Leaf Nodes and n2n_2n2 is the Number of Nodes with Degree
2, Then n0=n2+1n_0 = n_2 + 1n0=n2+1
Statement:
 Let n0n_0n0 represent the number of leaf nodes (nodes with degree 0).
 Let n2n_2n2 represent the number of nodes with degree 2 (nodes with two
children).
 The statement to prove is that n0=n2+1n_0 = n_2 + 1n0=n2+1.
Proof:
For a binary tree:
 Each node can have a degree of 0, 1, or 2:
o Degree 0: Leaf nodes (nodes with no children).
o Degree 1: Nodes with exactly one child.
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

o Degree 2: Nodes with exactly two children.

Let:
 nnn be the total number of nodes in the tree.
 n0n_0n0 be the number of leaf nodes (degree 0).
 n1n_1n1 be the number of nodes with degree 1.
 n2n_2n2 be the number of nodes with degree 2.
In a binary tree, we can use the relation between the number of nodes and
edges:
1. Since each edge connects a parent to a child, a binary tree with nnn nodes
has exactly n−1n - 1n−1 edges.
2. Now consider the sum of the degrees of all nodes. This sum must be equal
to the total number of edges, which is n−1n - 1n−1.
For a binary tree:
 Each node with degree 2 contributes 2 edges.
 Each node with degree 1 contributes 1 edge.
 Each node with degree 0 (leaf nodes) contributes 0 edges.
So, we can write:
n−1=2n2+n1n - 1 = 2n_2 + n_1n−1=2n2+n1
Additionally, since the total number of nodes nnn is the sum of all nodes with
degrees 0, 1, and 2:
n=n0+n1+n2n = n_0 + n_1 + n_2n=n0+n1+n2
Now, substitute n=n0+n1+n2n = n_0 + n_1 + n_2n=n0+n1+n2 into the
equation for edges:
n0+n1+n2−1=2n2+n1n_0 + n_1 + n_2 - 1 = 2n_2 + n_1n0+n1+n2−1=2n2+n1
Simplifying, we get:
n0−1=n2n_0 - 1 = n_2n0−1=n2
Therefore:
n0=n2+1n_0 = n_2 + 1n0=n2+1
This completes the proof that for any nonempty binary tree, the number of leaf
nodes n0n_0n0 is equal to the number of nodes with degree 2, n2n_2n2, plus
one.

Define Binary search tree. Write a recursive function to search for a key value CO4
in a binary search tree. Draw the BST for the following input: 50, 30, 10, 60,
80, 20, 70, 55, 35, 5.

A Binary Search Tree (BST) is a binary tree in which:

 The left subtree of a node contains only nodes with values less than the
node's value.
 The right subtree of a node contains only nodes with values greater than the
node's value.
 Both the left and right subtrees must also be binary search trees.

Recursive Function to Search for a Key in a Binary Search Tree

In C, we can write a recursive function to search for a key in a BST. The
function will:
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

 Return NULL if the tree is empty or if the key is not found.

 If the key is found, return the node.
 If the key is smaller than the root's key, recursively search in the left subtree.
 If the key is larger than the root's key, recursively search in the right subtree.
Here's how this function can be implemented in C:
c
Copy code
#include <stdio.h>
#include <stdlib.h>

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;
}

// Recursive function to insert a key in the BST

struct Node* insert(struct Node* node, int data) {
if (node == NULL) return createNode(data);

if (data < node->data)

node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);

return node;
}

// Recursive function to search for a key in the BST

struct Node* search(struct Node* root, int key) {
if (root == NULL || root->data == key)
return root;

if (key < root->data)

return search(root->left, key);
else
return search(root->right, key);
}

// Helper function to print search result

void printSearchResult(struct Node* result, int key) {
if (result != NULL)
printf("Key %d found in the BST.\n", key);
else
printf("Key %d not found in the BST.\n", key);
}

// Main function
int main() {
struct Node* root = NULL;
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering

int keys[] = {50, 30, 10, 60, 80, 20, 70, 55, 35, 5};
int n = sizeof(keys) / sizeof(keys[0]);

// Insert keys into the BST

for (int i = 0; i < n; i++) {
root = insert(root, keys[i]);
}

// Search for a key in the BST

int key = 55;
struct Node* result = search(root, key);
printSearchResult(result, key);

return 0;
}
In this code:
 The insert function inserts a new key into the BST, preserving the BST
properties.
 The search function searches for a specified key in the BST. If the key is
found, it returns a pointer to the node containing the key; otherwise, it
returns NULL.
 The printSearchResult helper function displays whether the key was
found.

Constructing the BST for the Given Input

For the input values 50, 30, 10, 60, 80, 20, 70, 55, 35, 5, we can construct the
BST step-by-step by inserting each value in order.
1. 50: This is the first value, so it becomes the root.
2. 30: Inserted to the left of 50 (since 30 < 50).
3. 10: Inserted to the left of 30 (since 10 < 30).
4. 60: Inserted to the right of 50 (since 60 > 50).
5. 80: Inserted to the right of 60 (since 80 > 60).
6. 20: Inserted to the right of 10 (since 20 > 10).
7. 70: Inserted to the left of 80 (since 70 < 80).
8. 55: Inserted to the left of 60 (since 55 < 60).
9. 35: Inserted to the right of 30 (since 35 > 30).
10. 5: Inserted to the left of 10 (since 5 < 10).
The resulting BST structure looks like this:
markdown
Copy code
50
/ \
30 60
/ \ / \
10 35 55 80
/ \ /
5 20 70
ATRIA INSTITUTE OF TECHNOLOGY
Anandanagar, Bengaluru – 560 024

Department of Computer Science & Engineering