LPU_Colab

admin.lpucolab438.examly.io/course

DSA_Unit 4_Lecture 28 Coding

Test Summary

No. of Sections: 1
No. of Questions: 14
Total Duration: 90 min

Section 1 - Coding
Section Summary

No. of Questions: 14
Duration: 90 min

Additional Instructions:

None
Q1.
Problem Statement

You need to implement a program to work with a Binary Search Tree (BST). The program
should provide the following functionalities:

Create a BST: The user will provide the number of nodes n to be inserted into the
BST. Then, the user will enter n integer values that should be inserted into the BST.
After inserting the values, the program should display a message indicating that the
BST with n nodes is ready to use.

Inorder Traversal: The program should perform an inorder traversal of the BST
and display the nodes in ascending order.

Preorder Traversal: The program should perform a preorder traversal of the BST
and display the nodes.

1/95
 Postorder Traversal: The program should perform a postorder traversal of the BST
and display the nodes.

Exit: The program should exit gracefully.

Implement the necessary functions and handle any possible error conditions.

Note: This kind of question will help in clearing TCS recruitment.

Input Format
The first input consists of the choice.

If the choice is 1, enter the number of elements (n) and the space-separated elements (i)
to be inserted into the tree.

If the choice is 2, print the in-order traversal.

If the choice is 3, print the pre-order traversal.

If the choice is 4, print the post-order traversal.

If the choice is 5, exit.

If the choice is greater than 5, print "Wrong choice".

(By default, all the test cases have all the choices from 1-5, but the n and i values keep
changing)

Refer to the sample input for a better understanding.

Output Format
The output prints the results based on the choice. Depending on the choice made by the
user, the program should output the appropriate messages or display the nodes of the
BST.

Refer to the sample output for a better understanding.

Constraints
The BST can have duplicate elements.

The maximum number of nodes (n) is 15.

2/95
The integer values can be in the range of 1 to102.

Sample Input Sample Output

1
5
12 78 96 34 55
2
3
4
5

BST with 5 nodes is ready to use!

BST Traversal in INORDER
12 34 55 78 96
BST Traversal in PREORDER
12 78 34 55 96
BST Traversal in POSTORDER
55 34 96 78 12

Sample Input Sample Output

1
9
7 9 6 3 2 1 4 5 8
2
4
5

BST with 9 nodes is ready to use!

BST Traversal in INORDER
1 2 3 4 5 6 7 8 9
BST Traversal in POSTORDER
1 2 5 4 3 6 8 9 7

Sample Input Sample Output

6
5

Wrong choice

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q2.
Problem Statement

Akil is studying binary trees and wants to create a program that allows him to build a
binary tree from user input and then calculate its height. He would like to implement the
binary tree using a linked representation where each node contains an integer value. Akil
wants to practice his coding skills and optimize the code to handle large inputs efficiently.

3/95
Help Akil by designing a program that fulfills his requirements.

Input Format
The input consists of a sequence of integers, where each integer represents a node value
in the binary tree.

The input terminates when Akil enters a value of -1, which indicates the end of the input
sequence.

Output Format
The output displays a single integer, which represents the height of the binary tree.

Refer to the sample output for the formatting specifications.

Constraints
The input integers will be non-negative, except for the termination value of -1.

The binary tree can have at most 102 nodes.

Each node value will fit within the range of a 32-bit signed integer.

Sample Input Sample Output

1
2
3
4
-1

Height of the tree is 4

Sample Input Sample Output

6
3
1
4
2
9
7
8
10
12
15
14
-1

Height of the tree is 12

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q3.

4/95
Problem Statement

Nirmala is interested in analyzing binary trees. She wants to write a program that takes a
series of positive integers as input and constructs a binary tree from them. After
constructing the tree, she needs to find the largest element present in the tree.

Nirmala seeks your help in writing the code for this task.

Input Format
The input consists of a series of positive integers, terminated by a negative integer (-1).

Each positive integer represents a node value that should be inserted into the tree.

The negative integer (-1) marks the end of the input and should not be included in the
tree.

Output Format
The output displays a single line containing the value of the largest element in the
constructed tree.

Refer to the sample output for the formatting specifications.

Constraints
All input integers (except for the terminating -1) will be positive integers.

The range of the positive integers will be from 1 to 103.

The number of input integers will not exceed 102.

The tree should be constructed based on the given input.

Sample Input Sample Output

1
2
3
4
-1

Maximum element is 4

Sample Input Sample Output

5/95
6
3
1
4
2
9
7
8
10
12
15
14
-1

Maximum element is 15

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q4.
Problem Statement

Imagine you are working on a database management system for a hospital. The system
stores patient records in a binary search tree, where each node represents a patient and
the key values are based on some attribute (e.g., patient ID, age, or medical condition).
Your task is to write a program that finds the kth smallest patient based on the chosen
attribute.

Consider the following patient ID tree:

50

/ \

30 70

/ \ / \

20 40 60 80

In this tree, each node represents a patient ID. For example, patient IDs 20, 30, 40, 50,
60, 70, and 80 are stored in the tree in ascending order. Your program should be able to
find the kth-smallest patient ID when given a value for k. For instance, if k = 3, the
program should return 40 as the 3rd-smallest patient ID.

Input Format
The input consists of a series of positive integers (greater than zero) separated by space.

6/95
The input ends when a value (-1) is entered.

The integers represent the elements to be inserted into the binary search tree.

Output Format
After inserting all the elements into the binary search tree, the program should take an
additional input k representing the k-th smallest element to be found in the BST.

The output displays the k-th smallest element in the BST.

Refer to the sample output for the formatting specifications.

Constraints
The input integers will be positive and greater than zero.

The number of elements in the binary search tree will be at most 1000.

1 <= k <= number of nodes in the BST.

Sample Input Sample Output

20
30
40
50
60
70
80
-1
3

Smallest kth value 40

Sample Input Sample Output

1
2
3
4
5
-1
2

Smallest kth value 2

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q5.
Problem Statement

7/95
Imagine you are working on a library management system that stores information about
books in a binary search tree. Each node in the tree represents a book, and the key
values are based on the ISBN (International Standard Book Number) of the books. Your
task is to write a program that searches for a book based on its ISBN.

Consider the following ISBN tree:

50

/ \

30 70

/\ / \

20 40 60 80

In this tree, each node represents a book's ISBN. The books are stored in such a way
that the left subtree of any node contains ISBNs smaller than the node's ISBN, and the
right subtree contains ISBNs greater than the node's ISBN. For example, in the given
tree, ISBN 30 is located in the left subtree of the root node, while ISBN 70 is located in
the right subtree.

Your program should be able to search for a given ISBN in the tree and return whether or
not it exists in the database. For instance, if the program is given ISBN 40, it should
return a "found" message indicating that the book is present in the database.

Note: The kind of question is asked in the HCL interview.

Input Format
The input consists of a series of positive integers (greater than zero) separated by space.

The input ends when -1 is entered.

The integers represent the elements to be inserted into the binary search tree.

Output Format
After inserting all the elements into the binary search tree, the program should take an
additional input representing the key to be searched in the BST.

If the key is present in the binary search tree, print <key> is present in the BST.

8/95
If the key is not present in the binary search tree, print <key> is not present in the BST.

Refer to the sample output for the formatting specifications.

Constraints
The input integers will be positive and greater than zero.

The number of elements in the binary search tree will be at most 100.

Sample Input Sample Output

50
30
70
20
40
60
-1
30

30 is present in the BST

Sample Input Sample Output

6
3
1
2
4
-1
10

10 is not present in the BST

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q6.
Problem Statement

Ragul wants to build a binary search tree (BST) and perform a key search operation on it.
He needs your help to accomplish this. Write a program that helps Ragul create a BST
and search for a specific key within it.

Note: This kind of question will help in clearing Wipro recruitment.

Input Format
The first line of input consists of the number of nodes n.

9/95
The second line of input consists of n uniquevalues for nodes, separated by a space.

The third line of input consists of the key to be searched.

Output Format
The output displays one of the following messages based on whether the key is found in
the binary search tree or not in the following format:

1. If the key is found in the binary search tree, print "The key <<key value>> is found
in the binary search tree"
2. If the key is not found in the binary search tree, print "The key <<key value>> is
not found in the binary search tree"

Refer to the sample output for the exact format.

Constraints
1 ≤ numNodes ≤ 10

Each node value is a unique integer.

1 <= key <= 1000

Sample Input Sample Output

7
101 102 103 105 106 108 110
102

The key 102 is found in the binary search tree

Sample Input Sample Output

7
101 102 103 105 106 108 110
115

The key 115 is not found in the binary search tree

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q7.
Problem Statement

Preethi is fascinated by trees, especially binary search trees. She wants to create a
binary search tree (BST) of characters and perform deletion operations on it. She wants
you to help her write a program.

10/95
Preethi needs a program that allows her to:

1. Create a binary search tree by inserting a series of characters.

2. Delete a specific character from the binary search tree.
3. Print the characters in the BST in an in-order traversal.

Note

1. Each character inserted into the binary search tree is a number, special character,
lowercase letter, or uppercase letter. The characters are inserted based on their
respective ASCII value.
2. All inserted characters into the binary search tree will be unique.

Input Format
The first line of input consists of the number of characters N.

The second line of input consists of N unique characters separated by a space.

The third line of input consists of the character M to be deleted.

Output Format
The output displays the in-order traversal of the given inputs after deleting the character
M.

Refer to the sample output for formatting specifications.

Constraints
1 ≤ N ≤ 50

Sample Input Sample Output

5
Z E W T Y
Y

E T W Z

Sample Input Sample Output

11/95
7
A 2 B b # c D
#

2 A B D b c

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q8.
Problem Statement

Kumar is studying data structures and is currently learning about Binary Search Trees
(BST). He wants to implement the operations of creating and displaying a Binary Search
Tree.

Write a program that takes a sequence of positive integers as input and constructs a
Binary Search Tree using these integers. After constructing the BST, the program should
display the nodes of the BST in ascending order.

Input Format
The input consists of a series of positive integers greater than zero, separated by a
space.

The input ends when -1 is entered.

The integers represent the elements to be inserted into the binary search tree.

Output Format
The output displays the elements of the binary search tree in ascending order (sorted
order), separated by space.

Refer to the sample output for the formatting specifications.

Constraints
The input integers > 0.

The number of elements in the binary search tree will be at most 100.

Sample Input Sample Output

1
2
3
4
5
-1

12/95
1 2 3 4 5

Sample Input Sample Output

7
6
4
5
3
-1

3 4 5 6 7

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q9.
Problem Statement

Josh is fascinated by binary trees, and he has learned about inserting elements into a
binary search tree and performing pre-order traversal. He decided to write a program to
practice these concepts. Help Josh write a program that inserts elements into a binary
search tree (BST) and performs a pre-order traversal.

Input Format
The first line of input contains an integer t, representing the number of elements Josh
wants to insert into the BST.

The following t lines each contain t integer values representing the data to be inserted
into the BST, separated by a space.

Output Format
The output displays a single line with space-separated integers representing the pre-
order traversal of the BST.

Refer to the sample output for the formatting specifications.

Constraints
1 ≤ t ≤ 100

1 <= data <= 1000

Sample Input Sample Output

5
10 5 15 3 7

10 5 3 7 15

Sample Input Sample Output

13/95
7
8 3 10 1 6 14 4

8 3 1 6 4 10 14

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q10.
Problem Statement

Revi is fascinated by binary search trees (BSTs) and wants to perform some operations
on them. He wishes to construct a binary search tree from a series of positive integers
and calculate the sum of all the nodes in the BST.

Write a program to help Revi implement these operations using the BST concept.

Input Format
The input consists of a series of positive integers (greater than zero) separated by a
space.

The input ends when -1 is entered.

The integers represent the elements to be inserted into the binary search tree.

Output Format
The output displays an integer value, which represents the sum of all the nodes in the
BST.

Refer to the sample output for formatting specifications.

Constraints
The input integers will be positive and greater than zero.

The number of elements in the binary search tree will be at most 100.

Sample Input Sample Output

5
3
7
2
4
9
-1

Sum of all nodes in the BST is 30

14/95
Sample Input Sample Output

6
3
1
4
2
-1

Sum of all nodes in the BST is 16

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q11.
Problem Statement

Kathir is learning about binary search trees (BSTs) in his computer science class. He has
just implemented a simple program to create a binary search tree and calculate the sum
of all its leaf nodes. Can you help him validate his code and solve some scenarios to test
it?

For example, consider a tree with the following structure:

/\

3 7

/\ \

2 4 9

In this tree, the leaf nodes are 2, 4, and 9. The program should compute the sum of these
leaf node elements, which is 2 + 4 + 9 = 15.

Input Format
The input consists of a series of positive integers as input, each on a separate line.

The input terminates when Kathir enters -1. This signifies the end of input.

You can assume that the input integers are unique.

Output Format
The output displays the sum of all the leaf nodes in the binary search tree in the following
format:

15/95
"Sum of all leaf nodes are <<value>>"

Refer to the sample output for the formatting specifications.

Constraints
All input integers will be positive integers (greater than 0).

The number of nodes in the binary tree is at most 100.

The value of each node is at most 100.

Sample Input Sample Output

5
3
7
2
4
9
-1

Sum of all leaf nodes are 15

Sample Input Sample Output

6
3
1
4
2
-1

Sum of all leaf nodes are 6

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q12.
Problem Statement

Gayu is studying data structures, and she wants to implement a program that performs
various operations on a Binary Search Tree (BST).

Gayu to create a Binary Search Tree (BST) and perform the following operations:

1. Create BST: Gayu can create a BST by providing the number of nodes (n) and a list
of n integer values. The program constructs the BST using these values.

16/95
 2. Print Postorder: Gayu can print the elements of the BST in postorder traversal,
which means that the program will display the values in the left subtree, then the
right subtree, and finally the root of each subtree.
3. Exit: Gayu can exit the program.

Input Format
The first input consists of the choice.

If the choice is 1, enter the number of elements (n) and the space-separated elements (i)
to be inserted into the tree.

If the choice is 2, print the post-order traversal.

If the choice is 3, exit.

If the choice is greater than 3, print "Wrong choice".

(By default, all the test cases have all the choices from 1–3, but the n and i values keep
changing.)

Refer to the sample input for a better understanding.

Output Format
The first line of output consists of the following format:

"BST with %d nodes is ready to use!\n", where %d is the number of nodes in the
BST.

The second line of output consists of the following format:

"BST Traversal in POSTORDER\n"

The third line of output consists of the following format:

A space-separated list of integers representing the elements of the BST in postorder

traversal.

The fourth line of output consists of the following format:

If input an invalid choice (other than 1, 2, or 3),

"Wrong choice\n"

Refer to the sample output for a better understanding.

Constraints

17/95
The BST can have duplicate elements.

The maximum number of nodes (n) is 15.

The integer values can be in the range of 1 to 102.

Sample Input Sample Output

1
5
12 78 96 34 55
2
3

BST with 5 nodes is ready to use!

BST Traversal in POSTORDER
55 34 96 78 12

Sample Input Sample Output

1
9
7 9 6 3 2 1 4 5 8
2
5
3

BST with 9 nodes is ready to use!

BST Traversal in POSTORDER
1 2 5 4 3 6 8 9 7
Wrong choice

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q13.
Problem Statement

Kamal is developing a program that finds the Kth smallest element in a Binary Search
Tree (BST). He plans to use the Morris Traversal technique to optimize the search
process. Your task is to assist Kamal in verifying and testing his code.

Implement a program that performs the following actions:

1. Build a Binary Search Tree (BST) by adding integers to it one by one.

2. Find and print the Kth smallest element in the BST.

Input Format

18/95
The first n lines of input consist of a series of positive integers (greater than zero)
separated by space.

The input ends when a value (-1) is entered.

The last input of an integer represents the elements to be inserted into the binary search
tree.

Output Format
After inserting all the elements into the binary search tree, the program should take an
additional input k representing the k-th smallest element to be found in the BST.

The output displays the k-th smallest element in the BST.

Refer to the sample output for the formatting specifications.

Constraints
The input integers will be positive and greater than zero.

The number of elements in the binary search tree will be at most 1000.

1 <= k <= number of nodes in the BST.

Sample Input Sample Output

20
30
40
50
60
70
80
-1
3

Smallest kth value 40

Sample Input Sample Output

1
2
3
4
5
-1
2

Smallest kth value 2

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Q14.

19/95
Problem Statement

Arun is developing a program that uses a Binary Search Tree (BST) to manage a
collection of integers. He has written the code to create a BST and search for elements
within it, but he needs your assistance in testing its functionality.

You are tasked with helping Arun by designing a program that performs the following
actions:

1. Build a Binary Search Tree (BST) by adding integers to it one by one.

2. Search for a specific integer in the BST to determine if it is present.

Input Format
The first n lines of input consist of a series of positive integers (greater than zero)
separated by space.

The input ends when -1 is entered.

The last line of input consists of an integer representing the elements to be inserted into
the binary search tree.

Output Format
The output displays one of the following messages:

If the key is present in the binary search tree, print <key> is present in the BST.

If the key is not present in the binary search tree, print <key> is not present in the BST.

Refer to the sample output for the formatting specifications.

Constraints
The input integers will be positive and greater than zero.

The number of elements in the binary search tree will be at most 100.

Sample Input Sample Output

20/95
50
30
70
20
40
60
-1
30

30 is present in the BST

Sample Input Sample Output

6
3
1
2
4
-1
10

10 is not present in the BST

Time Limit: - ms Memory Limit: - kb Code Size: - kb

Answer Key & Solution

Section 1 - Coding
Q1 Test Case Input Output

1
12
123 456 789 987 654 321 147 258 369 741 852 963
2
3
4
5

BST with 12 nodes is ready to use!

BST Traversal in INORDER
123 147 258 321 369 456 654 741 789 852 963 987
BST Traversal in PREORDER
123 456 321 147 258 369 789 654 741 987 852 963
BST Traversal in POSTORDER
258 147 369 321 741 654 963 852 987 789 456 123

Weightage - 10 Input Output

1
6
18 98 77 34 55 26
2
3
4
5

21/95
BST with 6 nodes is ready to use!
BST Traversal in INORDER
18 26 34 55 77 98
BST Traversal in PREORDER
18 98 77 34 26 55
BST Traversal in POSTORDER
26 55 34 77 98 18

Weightage - 10 Input Output

1
10
789 987 654 321 147 258 369 741 852 963
2
3
4
5

BST with 10 nodes is ready to use!

BST Traversal in INORDER
147 258 321 369 654 741 789 852 963 987
BST Traversal in PREORDER
789 654 321 147 258 369 741 987 852 963
BST Traversal in POSTORDER
258 147 369 321 741 654 963 852 987 789

Weightage - 20 Input Output

1
6
12 23 45 56 78 89
2
3
4
5

BST with 6 nodes is ready to use!

BST Traversal in INORDER
12 23 45 56 78 89
BST Traversal in PREORDER
12 23 45 56 78 89
BST Traversal in POSTORDER
89 78 56 45 23 12

Weightage - 20 Input Output

1
12
12 23 45 56 78 89 98 87 65 54 32 21
2
3
4
5

22/95
BST with 12 nodes is ready to use!
BST Traversal in INORDER
12 21 23 32 45 54 56 65 78 87 89 98
BST Traversal in PREORDER
12 23 21 45 32 56 54 78 65 89 87 98
BST Traversal in POSTORDER
21 32 54 65 87 98 89 78 56 45 23 12

Weightage - 40 Sample Input Sample Output

1
5
12 78 96 34 55
2
3
4
5

BST with 5 nodes is ready to use!

BST Traversal in INORDER
12 34 55 78 96
BST Traversal in PREORDER
12 78 34 55 96
BST Traversal in POSTORDER
55 34 96 78 12

Sample Input Sample Output

1
9
7 9 6 3 2 1 4 5 8
2
4
5

BST with 9 nodes is ready to use!

BST Traversal in INORDER
1 2 3 4 5 6 7 8 9
BST Traversal in POSTORDER
1 2 5 4 3 6 8 9 7

Sample Input Sample Output

6
5

Wrong choice

Solution

23/95
#include <iostream>
#include<stdlib.h>
using namespace std;
struct tnode
{
int data;
struct tnode *right;
struct tnode *left;
};

struct tnode *CreateBST(struct tnode *, int);

void Inorder(struct tnode *);
void Preorder(struct tnode *);
void Postorder(struct tnode *);

int main()
{
struct tnode *root = NULL;
int choice, item, n, i;
do
{
cin>>choice;
switch(choice)
{
case 1:
root = NULL;
cin>>n;
for(i = 1; i <= n; i++)
{
cin>>item;
root = CreateBST(root,item);
}
cout<<"BST with "<<n<<" nodes is ready to use!"<<"\n";
break;
case 2:
cout<<"BST Traversal in INORDER"<<"\n";
Inorder(root);
cout<<"\n";
break;
case 3:
cout<<"BST Traversal in PREORDER"<<"\n";
Preorder(root);
cout<<"\n";
break;
case 4:
cout<<"BST Traversal in POSTORDER"<<"\n";
Postorder(root);
cout<<"\n";
break;
case 5:
exit(0);
break;
default:
cout<<"Wrong choice"<<"\n";
break;
}

24/95
 } while(1);
return 0;
}

struct tnode *CreateBST(struct tnode *root, int item)

{
if(root == NULL)
{
root = (struct tnode *)malloc(sizeof(struct tnode));
root->left = root->right = NULL;
root->data = item;
return root;
}
else
{
if(item < root->data )
root->left = CreateBST(root->left,item);
else if(item > root->data )
root->right = CreateBST(root->right,item);
else
cout<<"Duplicate Element! Not Allowed"<<"\n";

return(root);
}
}

void Inorder(struct tnode *root)

{
if( root != NULL)
{
Inorder(root->left);
cout<<root->data<<" ";
Inorder(root->right);
}
}

void Preorder(struct tnode *root)

{
if( root != NULL)
{
cout<<root->data<<" ";
Preorder(root->left);
Preorder(root->right);
}
}

void Postorder(struct tnode *root)

{
if( root != NULL)
{
Postorder(root->left);
Postorder(root->right);
cout<<root->data<<" ";
}
}

25/95
Q2 Test Case Input Output

1
2
3
-1

Height of the tree is 3

Weightage - 10 Input Output

1
-1

Height of the tree is 1

Weightage - 10 Input Output

1
4
7
6
8
9
3
2
1
-1

Height of the tree is 9

Weightage - 15 Input Output

56
32
14
9
-1

Height of the tree is 4

Weightage - 15 Input Output

3
9
7
5
6
4
32
12
96
-1

Height of the tree is 9

26/95
Weightage - 25 Input Output

1
2
3
4
5
6
7
8
9
13
15
16
14
-1

Height of the tree is 13

Weightage - 25 Sample Input Sample Output

1
2
3
4
-1

Height of the tree is 4

Sample Input Sample Output

6
3
1
4
2
9
7
8
10
12
15
14
-1

Height of the tree is 12

Solution

27/95
#include <iostream>
using namespace std;

struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;

TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}

};

TreeNode* head = nullptr;

void append(int d) {
TreeNode* newnode = new TreeNode(d);

if (head == nullptr) {
head = newnode;
} else {
TreeNode* temp = head;
while (true) {
if (temp->left != nullptr) {
temp = temp->left;
} else {
temp->left = newnode;
break;
}
}
}
}

int height(TreeNode* node) {

if (node == nullptr)
return 0;
else {
int lheight = height(node->left);
int rheight = height(node->right);
if (lheight > rheight)
return (lheight + 1);
else
return (rheight + 1);
}
}

void deleteTree(TreeNode* node) {

if (node == nullptr)
return;

deleteTree(node->left);
deleteTree(node->right);
delete node;
}

int main() {
int d;
do {

28/95
 cin >> d;
if (d > 0)
append(d);
} while (d != -1);

int h = height(head);
cout << "Height of the tree is " << h;
deleteTree(head);
head = nullptr;

return 0;
}

Q3 Test Case Input Output

1
2
3
-1

Maximum element is 3

Weightage - 10 Input Output

1
-1

Maximum element is 1

Weightage - 10 Input Output

1
4
7
6
8
9
3
2
1
-1

Maximum element is 9

Weightage - 15 Input Output

56
32
14
9
-1

Maximum element is 56

Weightage - 15 Input Output

29/95
3
9
7
5
6
4
32
12
96
-1

Maximum element is 96

Weightage - 25 Input Output

1
2
3
4
5
6
7
8
9
13
15
16
14
-1

Maximum element is 16

Weightage - 25 Sample Input Sample Output

1
2
3
4
-1

Maximum element is 4

Sample Input Sample Output

30/95
6
3
1
4
2
9
7
8
10
12
15
14
-1

Maximum element is 15

Solution

31/95
#include <iostream>
#include <climits>
using namespace std;

struct node
{
int data;
struct node* left;
struct node* right;
};

struct node* head = NULL;

void append(int d)
{
struct node* newnode = new node;
newnode->data = d;
newnode->left = NULL;
newnode->right = NULL;

if (head == NULL)
{
head = newnode;
}
else
{
struct node* temp = head;
while (temp->left != NULL || temp->right != NULL)
{
if (temp->left != NULL)
{
temp = temp->left;
}
else
{
temp = temp->right;
}
}

if (temp->left == NULL)
temp->left = newnode;
else
temp->right = newnode;
}
}

int largestElement(struct node* temp)

{
if (temp == NULL)
return INT_MIN;

int maxVal = temp->data;

int leftMax = largestElement(temp->left);

int rightMax = largestElement(temp->right);

32/95
 maxVal = max(maxVal, max(leftMax, rightMax));

return maxVal;
}

int main()
{
int d;
do
{
cin >> d;
if (d > 0)
append(d);
} while (d != -1);

cout << "Maximum element is " << largestElement(head) << endl;

return 0;
}

Q4 Test Case Input Output

50
30
20
40
70
60
80
-1
4

Smallest kth value 50

Weightage - 10 Input Output

50
30
20
40
70
60
80
-1
6

Smallest kth value 70

Weightage - 10 Input Output

33/95
5
3
7
2
4
9
-1
4

Smallest kth value 5

Weightage - 15 Input Output

6
3
2
1
4
7
8
9
10
-1
2

Smallest kth value 2

Weightage - 15 Input Output

6
3
2
1
4
7
8
9
10
-1
9

Smallest kth value 10

Weightage - 25 Input Output

6
3
2
1
-1
4

Smallest kth value 6

Weightage - 25 Sample Input Sample Output

34/95
20
30
40
50
60
70
80
-1
3

Smallest kth value 40

Sample Input Sample Output

1
2
3
4
5
-1
2

Smallest kth value 2

Solution

35/95
#include<stdio.h>
using namespace std;
struct Node
{
int data;
Node *left,*right;
};
void append(Node **rootadd,int data)
{
Node *temp,*newnode;
temp = *rootadd;
newnode = new Node();
newnode->left = NULL;
newnode->data = data;
newnode->right = NULL;
if(*rootadd == NULL)
*rootadd = newnode;
else
{
while(1)
{
if(data > temp->data)
{
if(temp->right != NULL)
{
temp = temp->right;
}
else
{
temp->right = newnode;
break;
}
}
else
{
if(temp->left != NULL)
{
temp = temp->left;
}
else
{
temp->left = newnode;
break;
}
}
}
}
}
int KSmallestUsingMorris(Node *root, int k)
{
int count = 0;
int ksmall = -1;
Node *curr = root;
while (curr != NULL)
{
if (curr->left == NULL)

36/95
 {
count++;
if (count==k)
ksmall = curr->data;
curr = curr->right;
}
else
{
Node *pre = curr->left;
while (pre->right != NULL && pre->right != curr)
pre = pre->right;
if (pre->right==NULL)
{
pre->right = curr;
curr = curr->left;
}
else
{
pre->right = NULL;
count++;
if (count==k)
ksmall = curr->data;
curr = curr->right;
}
}
}
return ksmall;
}
int main()
{
Node *root = NULL;
int data,k;
do
{
sacnf("%d",&data);
if(data > 0)
append(&root,data);
}while(data > 0);
cin>>k;
printf("Smallest kth value %d",KSmallestUsingMorris(root,k));
return 0;
}

37/95
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *left,*right;
};
void append(Node **rootadd,int data)
{
Node *temp,*newnode;
temp = *rootadd;
newnode = new Node();
newnode->left = NULL;
newnode->data = data;
newnode->right = NULL;
if(*rootadd == NULL)
*rootadd = newnode;
else
{
while(1)
{
if(data > temp->data)
{
if(temp->right != NULL)
{
temp = temp->right;
}
else
{
temp->right = newnode;
break;
}
}
else
{
if(temp->left != NULL)
{
temp = temp->left;
}
else
{
temp->left = newnode;
break;
}
}
}
}
}
int KSmallestUsingMorris(Node *root, int k)
{
int count = 0;
int ksmall = -1;
Node *curr = root;
while (curr != NULL)
{

38/95
 if (curr->left == NULL)
{
count++;
if (count==k)
ksmall = curr->data;
curr = curr->right;
}
else
{
Node *pre = curr->left;
while (pre->right != NULL && pre->right != curr)
pre = pre->right;
if (pre->right==NULL)
{
pre->right = curr;
curr = curr->left;
}
else
{
pre->right = NULL;
count++;
if (count==k)
ksmall = curr->data;
curr = curr->right;
}
}
}
return ksmall;
}
int main()
{
Node *root = NULL;
int data,k;
do
{
cin>>data;
if(data > 0)
append(&root,data);
}while(data > 0);
cin>>k;
cout<<"Smallest kth value "<<KSmallestUsingMorris(root,k);
return 0;
}

Q5 Test Case Input Output

6
3
1
2
4
-1
4

4 is present in the BST

39/95
Weightage - 10 Input Output

6
3
1
2
4
-1
3

3 is present in the BST

Weightage - 10 Input Output

6
3
2
1
4
10
9
8
7
15
-1
10

10 is present in the BST

Weightage - 15 Input Output

6
3
2
1
4
10
9
8
7
15
-1
14

14 is not present in the BST

Weightage - 15 Input Output

40/95
6
3
2
1
4
10
9
8
7
15
-1
7

7 is present in the BST

Weightage - 25 Input Output

6
3
2
1
4
10
9
8
7
15
-1
16

16 is not present in the BST

Weightage - 25 Sample Input Sample Output

50
30
70
20
40
60
-1
30

30 is present in the BST

Sample Input Sample Output

6
3
1
2
4
-1
10

10 is not present in the BST

41/95
Solution

42/95
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node*left;
struct node*right;
};
struct node*root;
void append(int d)//3
{
struct node*newnode = (struct node*)malloc(sizeof(struct node));
struct node*temp = root;//6
newnode->data = d;//3
newnode->left = NULL;
newnode->right = NULL;
if(root == NULL)//6
{
root = newnode;//6
}
else
{
while(true)
{
if(d < temp->data)
{
if(temp->left != NULL)
{
temp = temp->left;
}
else
{
temp->left = newnode;//6->3
break;
}
}else
{
if(temp->right != NULL)
{
temp = temp->right;
}else
{
temp->right = newnode;
break;
}
}
}
}
}
bool iterativesearch(struct node*root,int key)
{
while(root != NULL)//10
{
if(key > root->data)
{
root = root->right;//10

43/95
 }
else if(key < root->data)
{
root = root->left;
}
else
return true;
}
return false;
}
int main()
{
int d,search;
do
{
scanf("%d",&d);//3
if(d > 0)
append(d);
}while(d != -1);//-1
scanf("%d",&search);
if(iterativesearch(root,search))
cout<<search<<" is present in the BST";
else
cout<<search<<" is not present in the BST";
return 0;
}

44/95
#include<iostream>
#include<cstdlib>
using namespace std;
struct node
{
int data;
struct node*left;
struct node*right;
};
struct node*root;
void append(int d)//3
{
struct node*newnode = (struct node*)malloc(sizeof(struct node));
struct node*temp = root;//6
newnode->data = d;//3
newnode->left = NULL;
newnode->right = NULL;
if(root == NULL)//6
{
root = newnode;//6
}
else
{
while(true)
{
if(d < temp->data)
{
if(temp->left != NULL)
{
temp = temp->left;
}
else
{
temp->left = newnode;//6->3
break;
}
}else
{
if(temp->right != NULL)
{
temp = temp->right;
}else
{
temp->right = newnode;
break;
}
}
}
}
}
bool iterativesearch(struct node*root,int key)
{
while(root != NULL)//10
{
if(key > root->data)
{

45/95
 root = root->right;//10
}
else if(key < root->data)
{
root = root->left;
}
else
return true;
}
return false;
}
int main()
{
int d,search;
do
{
cin>>d;//3
if(d > 0)
append(d);
}while(d != -1);//-1
cin>>search;
if(iterativesearch(root,search))
cout<<search<<" is present in the BST";
else
cout<<search<<" is not present in the BST";
return 0;
}

Q6 Test Case Input Output

5
60 40 80 30 50
14

The key 14 is not found in the binary search tree

Weightage - 10 Input Output

5
60 40 80 30 50
50

The key 50 is found in the binary search tree

Weightage - 10 Input Output

9
45 25 65 15 35 55 75 5 95
45

The key 45 is found in the binary search tree

Weightage - 15 Input Output

46/95
9
45 25 65 15 35 55 75 5 95
100

The key 100 is not found in the binary search tree

Weightage - 15 Input Output

10
100 50 150 25 75 125 175 60 74 85
150

The key 150 is found in the binary search tree

Weightage - 25 Input Output

10
100 50 150 25 75 125 175 60 74 85
15

The key 15 is not found in the binary search tree

Weightage - 25 Sample Input Sample Output

7
101 102 103 105 106 108 110
102

The key 102 is found in the binary search tree

Sample Input Sample Output

7
101 102 103 105 106 108 110
115

The key 115 is not found in the binary search tree

Solution

47/95
#include <iostream>
using namespace std;

struct Node {
int data;
Node* left;
Node* right;
};

Node* createNode(int value) {

Node* newNode = new Node();
if (!newNode) {
return NULL;
}
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}

Node* insertNode(Node* root, int value) {

if (root == NULL) {
return createNode(value);
}

if (value < root->data) {

root->left = insertNode(root->left, value);
} else if (value > root->data) {
root->right = insertNode(root->right, value);
}

return root;
}

bool searchKey(Node* root, int key) {

while (root != NULL) {
if (key == root->data) {
return true;
} else if (key < root->data) {
root = root->left;
} else {
root = root->right;
}
}
return false;
}

int main() {
Node* root = NULL;
int numNodes, value, key;

cin >> numNodes;

for (int i = 0; i < numNodes; i++) {

cin >> value;
root = insertNode(root, value);
}

48/95
 cin >> key;

bool found = searchKey(root, key);

if (found) {
cout << "The key " << key << " is found in the binary search tree";
} else {
cout << "The key " << key << " is not found in the binary search tree";
}

return 0;
}

49/95
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* left;
struct Node* right;
};

struct Node* createNode(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
return NULL;
}
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}

struct Node* insertNode(struct Node* root, int value) {

if (root == NULL) {
return createNode(value);
}

if (value < root->data) {

root->left = insertNode(root->left, value);
} else if (value > root->data) {
root->right = insertNode(root->right, value);
}

return root;
}

int searchKey(struct Node* root, int key) {

while (root != NULL) {
if (key == root->data) {
return 1; // Key found
} else if (key < root->data) {
root = root->left;
} else {
root = root->right;
}
}
return 0; // Key not found
}

int main() {
struct Node* root = NULL;
int numNodes, value, key;

scanf("%d", &numNodes);

for (int i = 0; i < numNodes; i++) {

scanf("%d", &value);
root = insertNode(root, value);
}

50/95
 scanf("%d", &key);

int found = searchKey(root, key);

if (found) {
printf("The key %d is found in the binary search tree", key);
} else {
printf("The key %d is not found in the binary search tree", key);
}

return 0;
}

Q7 Test Case Input Output

10
! @ # $ % ^ & * ( )
@

! # $ % & ( ) * ^

Weightage - 20 Input Output

20
m a l r g z q k i d h f j n o p e A Y U
U

A Y a d e f g h i j k l m n o p q r z

Weightage - 25 Input Output

30
C D 1 9 2 G 7 K P F T A H 5 N Z Q M X R B Y E 6 J 8 U V L !
C

! 1 2 5 6 7 8 9 A B D E F G H J K L M N P Q R T U V X Y Z

Weightage - 25 Input Output

50
q R 1 b S c 2 t V u x H N i 9 g Y 7 O K P 8 W 6 Z a j 5 m E 4 B d C L f X p n h 0
J k 3 o I v M y s
0

1 2 3 4 5 6 7 8 9 B C E H I J K L M N O P R S V W X Y Z a b c d f g h i j k m n o
p q s t u v x y

Weightage - 30 Sample Input Sample Output

5
Z E W T Y
Y

E T W Z

Sample Input Sample Output

51/95
7
A 2 B b # c D
#

2 A B D b c

Solution

52/95
#include <iostream>
using namespace std;
struct Node {
char data;
Node* left;
Node* right;
};

Node* insert(Node* root, char data) {

if (root == NULL) {
root = new Node();
root->data = data;
root->left = root->right = NULL;
} else if (data <= root->data) {
root->left = insert(root->left, data);
} else {
root->right = insert(root->right, data);
}
return root;
}

Node* findMin(Node* root) {

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

Node* deleteNode(Node* root, char data) {

if (root == NULL) {
return root;
} else if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
if (root->left == NULL && root->right == NULL) {
delete root;
root = NULL;
} else if (root->left == NULL) {
Node* temp = root;
root = root->right;
delete temp;
} else if (root->right == NULL) {
Node* temp = root;
root = root->left;
delete temp;
} else {
Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
return root;
}

53/95
void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}

int main() {
int size;
cin >> size;
Node* root = NULL;
char input, char_to_delete;
while(size!=0) {
cin >> input;
root = insert(root, input);
size--;
}
cin >> char_to_delete;
root = deleteNode(root, char_to_delete);
inorder(root);
cout << endl;
return 0;
}

54/95
#include <stdio.h>
#include <stdlib.h>

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

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

struct Node* insert(struct Node* root, char data) {

if (root == NULL) {
return createNode(data);
} else if (data <= root->data) {
root->left = insert(root->left, data);
} else {
root->right = insert(root->right, data);
}
return root;
}

struct Node* findMin(struct Node* root) {

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

struct Node* deleteNode(struct Node* root, char data) {

if (root == NULL) {
return root;
} else if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
if (root->left == NULL && root->right == NULL) {
free(root);
root = NULL;
} else if (root->left == NULL) {
struct Node* temp = root;
root = root->right;
free(temp);
} else if (root->right == NULL) {
struct Node* temp = root;
root = root->left;
free(temp);
} else {
struct Node* temp = findMin(root->right);

55/95
 root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
return root;
}

void inorder(struct Node* root) {

if (root != NULL) {
inorder(root->left);
printf("%c ", root->data);
inorder(root->right);
}
}

int main() {
int size;
scanf("%d", &size);
struct Node* root = NULL;
char input, char_to_delete;
while (size != 0) {
scanf(" %c", &input);
root = insert(root, input);
size--;
}
scanf(" %c", &char_to_delete);
root = deleteNode(root, char_to_delete);
inorder(root);
printf("\n");
return 0;
}

Q8 Test Case Input Output

6
3
2
1
4
7
8
9
10
-1

1 2 3 4 6 7 8 9 10

Weightage - 10 Input Output

5
3
7
2
4
9
-1

56/95
2 3 4 5 7 9

Weightage - 10 Input Output

6
3
2
1
-1

1 2 3 6

Weightage - 15 Input Output

11
56
45
78
-1

11 45 56 78

Weightage - 15 Input Output

7
3
6
9
4
1
5
4
9
-1

1 3 4 4 5 6 7 9 9

Weightage - 25 Input Output

79
46
64
95
12
145
63
32
-1

12 32 46 63 64 79 95 145

Weightage - 25 Sample Input Sample Output

57/95
1
2
3
4
5
-1

1 2 3 4 5

Sample Input Sample Output

7
6
4
5
3
-1

3 4 5 6 7

Solution

58/95
#include<stdio.h>
#include<stdlib.h>
using namespace std;
struct node
{
int data;
struct node*left;
struct node*right;
};
struct node*root;
void append(int d)//3
{
struct node*newnode = (struct node*)malloc(sizeof(struct node));
struct node*temp = root;//6
newnode->data = d;//3
newnode->left = NULL;
newnode->right = NULL;
if(root == NULL)//6
{
root = newnode;//6
}
else
{
while(true)
{
if(d < temp->data)
{
if(temp->left != NULL)
{
temp = temp->left;
}
else
{
temp->left = newnode;//6->3
break;
}
}else
{
if(temp->right != NULL)
{
temp = temp->right;
}else
{
temp->right = newnode;
break;
}
}
}
}
}
void display(struct node*root)
{
if(root == NULL)
{
return;
}

59/95
 else
{
display(root->left);
printf("%d ",root->data);
display(root->right);
}
}
int main()
{
int d;
do
{
scanf("%d",&d);//3
if(d > 0)
append(d);
}while(d != -1);//-1
display(root);
return 0;
}

60/95
#include<iostream>
#include<cstdlib>
using namespace std;
struct node
{
int data;
struct node*left;
struct node*right;
};
struct node*root;
void append(int d)
{
struct node*newnode = (struct node*)malloc(sizeof(struct node));
struct node*temp = root;
newnode->data = d;
newnode->left = NULL;
newnode->right = NULL;
if(root == NULL)
{
root = newnode;
}
else
{
while(true)
{
if(d < temp->data)
{
if(temp->left != NULL)
{
temp = temp->left;
}
else
{
temp->left = newnode;
break;
}
}else
{
if(temp->right != NULL)
{
temp = temp->right;
}else
{
temp->right = newnode;
break;
}
}
}
}
}
void display(struct node*root)
{
if(root == NULL)
{
return;
}

61/95
 else
{
display(root->left);
cout<<root->data<<" ";
display(root->right);
}
}
int main()
{
int d;
do
{
cin>>d;//3
if(d > 0)
append(d);
}while(d != -1);//-1
display(root);
return 0;
}

Q9 Test Case Input Output

11
9 3 5 1 8 12 16 11 2 4 6

9 3 1 2 5 4 8 6 12 11 16

Weightage - 25 Input Output

7
1 8 12 16 11 2 4

1 8 2 4 12 11 16

Weightage - 10 Input Output

8
8 4 9 1 2 3 6 5

8 4 1 2 3 6 5 9

Weightage - 15 Input Output

26
23 16 15 9 6 17 10 13 8 26 18 2 22 24 12 5 20 25 21 4 19 1 3 14 7 11

23 16 15 9 6 2 1 5 4 3 8 7 10 13 12 11 14 17 18 22 20 19 21 26 24 25

Weightage - 25 Input Output

9
7 9 4 2 6 3 5 1 8

7 4 2 1 3 6 5 9 8

Weightage - 15 Input Output

62/95
1
5

Weightage - 10 Sample Input Sample Output

5
10 5 15 3 7

10 5 3 7 15

Sample Input Sample Output

7
8 3 10 1 6 14 4

8 3 1 6 4 10 14

Solution

63/95
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct node {

int data;
struct node *left;
struct node *right;

};

void preOrder( struct node *root) {

if( root == NULL )

return;
printf("%d ",root->data);
preOrder(root->left);
preOrder(root->right);

struct node* insert( struct node* root, int data ) {

if(root == NULL){
root = malloc(sizeof(struct node));
root->data = data;
root->left = NULL;
root->right = NULL;

}else if(data < root->data){

root->left = insert(root->left, data);
}else{
root->right = insert(root->right, data);
}
return root;

int main() {

struct node* root = NULL;

int t;
int data;

scanf("%d", &t);

while(t-- > 0) {
scanf("%d", &data);
root = insert(root, data);
}

64/95
 preOrder(root);
return 0;
}

#include <iostream>
using namespace std;

struct Node {
int data;
Node* left;
Node* right;
};

void preOrder(Node* root) {

if (root == nullptr)
return;
cout << root->data << " ";
preOrder(root->left);
preOrder(root->right);
}

Node* insert(Node* root, int data) {

if (root == nullptr) {
root = new Node();
root->data = data;
root->left = nullptr;
root->right = nullptr;
} else if (data < root->data) {
root->left = insert(root->left, data);
} else {
root->right = insert(root->right, data);
}
return root;
}

int main() {
Node* root = nullptr;

int t;
int data;

cin >> t;

while (t-- > 0) {

cin >> data;
root = insert(root, data);
}

preOrder(root);
return 0;
}

Q10 Test Case Input Output

65/95
1
2
3
4
5
-1

Sum of all nodes in the BST is 15

Weightage - 10 Input Output

10
20
30
40
50
-1

Sum of all nodes in the BST is 150

Weightage - 10 Input Output

1
3
5
7
4
8
9
-1

Sum of all nodes in the BST is 37

Weightage - 15 Input Output

79
46
13
25
28
-1

Sum of all nodes in the BST is 191

Weightage - 15 Input Output

79
95
48
12
26
35
65
48
-1

66/95
Sum of all nodes in the BST is 360

Weightage - 25 Input Output

76
67
98
15
11
13
15
14
61
63
56
-1

Sum of all nodes in the BST is 474

Weightage - 25 Sample Input Sample Output

5
3
7
2
4
9
-1

Sum of all nodes in the BST is 30

Sample Input Sample Output

6
3
1
4
2
-1

Sum of all nodes in the BST is 16

Solution

67/95
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node*left;
struct node*right;
};
struct node*root;

//Function to create binary search tree

void append(int d)
{
struct node*newnode = (struct node*)malloc(sizeof(struct node));
struct node*temp = root;
newnode->data = d;//2
newnode->left = NULL;
newnode->right = NULL;
if(root == NULL)
{
root = newnode;
}
else
{
while(true)
{
if(d < temp->data)
{
if(temp->left != NULL)
{
temp = temp->left;
}else
{
temp->left = newnode;
break;
}
}else
{
if(temp->right != NULL)
{
temp = temp->right;
}else
{
temp->right = newnode;
break;
}
}
}
}
}
int addBT(node* root)
{
if(root == NULL)
return 0;
return (root->data+addBT(root->left)+addBT(root->right));

68/95
}
int main()
{
int d;
do
{
scanf("%d",&d);
if(d > 0)
append(d);
}while(d != -1);
int sum = addBT(root);
printf("Sum of all nodes are %d",sum);
return 0;
}

69/95
#include<iostream>
#include<cstdlib>
using namespace std;

struct node
{
int data;
struct node* left;
struct node* right;
};

struct node* root;

struct node* createNode(int d)

{
struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = d;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}

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

{
if (root == NULL)
return createNode(value);

if (value < root->data)

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

return root;
}

int addBST(struct node* root)

{
if (root == NULL)
return 0;

return (root->data + addBST(root->left) + addBST(root->right));

}

int main()
{
int d;
do
{
cin >> d;
if (d > 0)
root = insert(root, d);
} while (d != -1);

int sum = addBST(root);

cout << "Sum of all nodes in the BST is " << sum;

70/95
 return 0;
}

Q11 Test Case Input Output

1
2
3
4
5
-1

Sum of all leaf nodes are 5

Weightage - 10 Input Output

10
20
30
40
50
-1

Sum of all leaf nodes are 50

Weightage - 10 Input Output

1
3
5
7
4
8
9
-1

Sum of all leaf nodes are 13

Weightage - 15 Input Output

79
46
13
25
28
-1

Sum of all leaf nodes are 28

Weightage - 15 Input Output

71/95
79
95
48
12
26
35
65
48
-1

Sum of all leaf nodes are 178

Weightage - 25 Input Output

76
67
98
15
11
13
15
14
61
63
56
-1

Sum of all leaf nodes are 231

Weightage - 25 Sample Input Sample Output

5
3
7
2
4
9
-1

Sum of all leaf nodes are 15

Sample Input Sample Output

6
3
1
4
2
-1

Sum of all leaf nodes are 6

Solution

72/95
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node*left;
struct node*right;
};
struct node*root;
void append(int d)
{
struct node*newnode = (struct node*)malloc(sizeof(struct node));
struct node*temp = root;
newnode->data = d;
newnode->left = NULL;
newnode->right = NULL;
if(root == NULL)
{
root = newnode;
}
else
{
while(true)
{
if(d < temp->data)
{
if(temp->left != NULL)
{
temp = temp->left;
}else
{
temp->left = newnode;
break;
}
}else
{
if(temp->right != NULL)
{
temp = temp->right;
}else
{
temp->right = newnode;
break;
}
}
}
}
}
void leafsum(node *root,int *sum)
{
if(!root)
return;
if(!root->left && !root->right)
*sum+= root->data;
leafsum(root->left,sum);
leafsum(root->right,sum);

73/95
}
int main()
{
int d;
do
{
scanf("%d",&d);
if(d > 0)
append(d);
}while(d != -1);
int sum = 0;
leafsum(root,&sum);
printf("Sum of all leaf nodes are %d",sum);
return 0;
}

74/95
#include<iostream>
#include<cstdlib>
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* root;

struct node* createNode(int d)

{
struct node* newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = d;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}

void append(int d)
{
struct node* newnode = createNode(d);
struct node* temp = root;
if (root == NULL)
{
root = newnode;
}
else
{
while (true)
{
if (d < temp->data)
{
if (temp->left != NULL)
{
temp = temp->left;
}
else
{
temp->left = newnode;
break;
}
}
else
{
if (temp->right != NULL)
{
temp = temp->right;
}
else
{
temp->right = newnode;
break;
}
}

75/95
 }
}
}

void leafsum(node* root, int* sum)

{
if (!root)
return;
if (!root->left && !root->right)
*sum += root->data;
leafsum(root->left, sum);
leafsum(root->right, sum);
}

int main()
{
int d;
do
{
cin >> d;
if (d > 0)
append(d);
} while (d != -1);
int sum = 0;
leafsum(root, &sum);
cout << "Sum of all leaf nodes are " << sum;
return 0;
}

Q12 Test Case Input Output

6
5

Wrong choice

Weightage - 10 Input Output

1
12
123 456 789 987 654 321 147 258 369 741 852 963
2
3

BST with 12 nodes is ready to use!

BST Traversal in POSTORDER
258 147 369 321 741 654 963 852 987 789 456 123

Weightage - 25 Input Output

1
6
18 98 77 34 55 26
2
3

76/95
BST with 6 nodes is ready to use!
BST Traversal in POSTORDER
26 55 34 77 98 18

Weightage - 10 Input Output

1
10
789 987 654 321 147 258 369 741 852 963
2
3

BST with 10 nodes is ready to use!

BST Traversal in POSTORDER
258 147 369 321 741 654 963 852 987 789

Weightage - 15 Input Output

1
6
12 23 45 56 78 89
2
3

BST with 6 nodes is ready to use!

BST Traversal in POSTORDER
89 78 56 45 23 12

Weightage - 15 Input Output

1
12
12 23 45 56 78 89 98 87 65 54 32 21
2
3

BST with 12 nodes is ready to use!

BST Traversal in POSTORDER
21 32 54 65 87 98 89 78 56 45 23 12

Weightage - 25 Sample Input Sample Output

1
5
12 78 96 34 55
2
3

BST with 5 nodes is ready to use!

BST Traversal in POSTORDER
55 34 96 78 12

Sample Input Sample Output

77/95
1
9
7 9 6 3 2 1 4 5 8
2
5
3

BST with 9 nodes is ready to use!

BST Traversal in POSTORDER
1 2 5 4 3 6 8 9 7
Wrong choice

Solution

78/95
#include <iostream>
#include <stdlib.h>

using namespace std;

struct tnode {
int data;
struct tnode *right;
struct tnode *left;
};

struct tnode *CreateBST(struct tnode *, int);

void Postorder(struct tnode *);

struct tnode *CreateBST(struct tnode *root, int item) {

if (root == NULL) {
root = (struct tnode *) malloc(sizeof(struct tnode));
root->left = root->right = NULL;
root->data = item;
return root;
} else {
if (item < root->data)
root->left = CreateBST(root->left, item);
else if (item > root->data)
root->right = CreateBST(root->right, item);
// Ignore duplicates
return root;
}
}

void Postorder(struct tnode *root) {

if (root != NULL) {
Postorder(root->left);
Postorder(root->right);
cout << root->data << " ";
}
}

int main() {
struct tnode *root = NULL;
int choice, item, n, i;
do {
cin >> choice;
switch (choice) {
case 1:
root = NULL;
cin >> n;
for (i = 1; i <= n; i++) {
cin >> item;
root = CreateBST(root, item);
}
cout << "BST with " << n << " nodes (without duplicates) is ready
to use!" << "\n";
break;
case 2:
cout << "BST Traversal in POSTORDER" << "\n";

79/95
 Postorder(root);
cout << "\n";
break;
case 3:
exit(0);
break;
default:
cout << "Wrong choice" << "\n";
break;
}
} while (1);
return 0;
}

80/95
#include <stdio.h>
#include <stdlib.h>

struct tnode {
int data;
struct tnode *right;
struct tnode *left;
};

struct tnode *CreateBST(struct tnode *, int);

void Postorder(struct tnode *);

struct tnode *CreateBST(struct tnode *root, int item) {

if (root == NULL) {
root = (struct tnode *) malloc(sizeof(struct tnode));
root->left = root->right = NULL;
root->data = item;
return root;
} else {
if (item < root->data)
root->left = CreateBST(root->left, item);
else if (item > root->data)
root->right = CreateBST(root->right, item);

return (root);
}
}

void Postorder(struct tnode *root) {

if (root != NULL) {
Postorder(root->left);
Postorder(root->right);
printf("%d ", root->data);
}
}

int main() {
struct tnode *root = NULL;
int choice, item, n, i;
do {
scanf("%d", &choice);
switch (choice) {
case 1:
root = NULL;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
scanf("%d", &item);
root = CreateBST(root, item);
}
printf("BST with %d nodes is ready to use!\n", n);
break;
case 2:
printf("BST Traversal in POSTORDER\n");
Postorder(root);
printf("\n");
break;

81/95
 case 3:
exit(0);
break;
default:
printf("Wrong choice\n");
break;
}
} while (1);
return 0;
}

Q13 Test Case Input Output

50
30
20
40
70
60
80
-1
4

Smallest kth value 50

Weightage - 10 Input Output

50
30
20
40
70
60
80
-1
6

Smallest kth value 70

Weightage - 10 Input Output

5
3
7
2
4
9
-1
4

Smallest kth value 5

Weightage - 15 Input Output

82/95
6
3
2
1
4
7
8
9
10
-1
2

Smallest kth value 2

Weightage - 15 Input Output

6
3
2
1
4
7
8
9
10
-1
9

Smallest kth value 10

Weightage - 25 Input Output

6
3
2
1
-1
4

Smallest kth value 6

Weightage - 25 Sample Input Sample Output

20
30
40
50
60
70
80
-1
3

Smallest kth value 40

Sample Input Sample Output

83/95
1
2
3
4
5
-1
2

Smallest kth value 2

Solution

84/95
#include<stdio.h>
using namespace std;
struct Node
{
int data;
Node *left,*right;
};
void append(Node **rootadd,int data)
{
Node *temp,*newnode;
temp = *rootadd;
newnode = new Node();
newnode->left = NULL;
newnode->data = data;
newnode->right = NULL;
if(*rootadd == NULL)
*rootadd = newnode;
else
{
while(1)
{
if(data > temp->data)
{
if(temp->right != NULL)
{
temp = temp->right;
}
else
{
temp->right = newnode;
break;
}
}
else
{
if(temp->left != NULL)
{
temp = temp->left;
}
else
{
temp->left = newnode;
break;
}
}
}
}
}
int KSmallestUsingMorris(Node *root, int k)
{
int count = 0;
int ksmall = -1;
Node *curr = root;
while (curr != NULL)
{
if (curr->left == NULL)

85/95
 {
count++;
if (count==k)
ksmall = curr->data;
curr = curr->right;
}
else
{
Node *pre = curr->left;
while (pre->right != NULL && pre->right != curr)
pre = pre->right;
if (pre->right==NULL)
{
pre->right = curr;
curr = curr->left;
}
else
{
pre->right = NULL;
count++;
if (count==k)
ksmall = curr->data;
curr = curr->right;
}
}
}
return ksmall;
}
int main()
{
Node *root = NULL;
int data,k;
do
{
sacnf("%d",&data);
if(data > 0)
append(&root,data);
}while(data > 0);
cin>>k;
printf("Smallest kth value %d",KSmallestUsingMorris(root,k));
return 0;
}

86/95
#include <iostream>
using namespace std;

struct Node
{
int data;
Node *left, *right;
};

void append(Node **rootadd, int data)

{
Node *temp, *newnode;
temp = *rootadd;
newnode = new Node();
newnode->left = NULL;
newnode->data = data;
newnode->right = NULL;
if (*rootadd == NULL)
*rootadd = newnode;
else
{
while (1)
{
if (data > temp->data)
{
if (temp->right != NULL)
{
temp = temp->right;
}
else
{
temp->right = newnode;
break;
}
}
else
{
if (temp->left != NULL)
{
temp = temp->left;
}
else
{
temp->left = newnode;
break;
}
}
}
}
}

int KSmallestUsingMorris(Node *root, int k)

{
int count = 0;
int ksmall = -1;
Node *curr = root;

87/95
 while (curr != NULL)
{
if (curr->left == NULL)
{
count++;
if (count == k)
ksmall = curr->data;
curr = curr->right;
}
else
{
Node *pre = curr->left;
while (pre->right != NULL && pre->right != curr)
pre = pre->right;
if (pre->right == NULL)
{
pre->right = curr;
curr = curr->left;
}
else
{
pre->right = NULL;
count++;
if (count == k)
ksmall = curr->data;
curr = curr->right;
}
}
}
return ksmall;
}

int main()
{
Node *root = NULL;
int data, k;
do
{
cin >> data;
if (data > 0)
append(&root, data);
} while (data > 0);
cin >> k;
cout << "Smallest kth value " << KSmallestUsingMorris(root, k);
return 0;
}

Q14 Test Case Input Output

6
3
1
2
4
-1
4

88/95
4 is present in the BST

Weightage - 10 Input Output

6
3
1
2
4
-1
3

3 is present in the BST

Weightage - 10 Input Output

6
3
2
1
4
10
9
8
7
15
-1
10

10 is present in the BST

Weightage - 15 Input Output

6
3
2
1
4
10
9
8
7
15
-1
14

14 is not present in the BST

Weightage - 15 Input Output

89/95
6
3
2
1
4
10
9
8
7
15
-1
7

7 is present in the BST

Weightage - 25 Input Output

6
3
2
1
4
10
9
8
7
15
-1
16

16 is not present in the BST

Weightage - 25 Sample Input Sample Output

50
30
70
20
40
60
-1
30

30 is present in the BST

Sample Input Sample Output

6
3
1
2
4
-1
10

10 is not present in the BST

90/95
Solution

91/95
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node*left;
struct node*right;
};
struct node*root;
void append(int d)//3
{
struct node*newnode = (struct node*)malloc(sizeof(struct node));
struct node*temp = root;//6
newnode->data = d;//3
newnode->left = NULL;
newnode->right = NULL;
if(root == NULL)//6
{
root = newnode;//6
}
else
{
while(true)
{
if(d < temp->data)
{
if(temp->left != NULL)
{
temp = temp->left;
}
else
{
temp->left = newnode;//6->3
break;
}
}else
{
if(temp->right != NULL)
{
temp = temp->right;
}else
{
temp->right = newnode;
break;
}
}
}
}
}
bool iterativesearch(struct node*root,int key)
{
while(root != NULL)//10
{
if(key > root->data)
{
root = root->right;//10

92/95
 }
else if(key < root->data)
{
root = root->left;
}
else
return true;
}
return false;
}
int main()
{
int d,search;
do
{
scanf("%d",&d);//3
if(d > 0)
append(d);
}while(d != -1);//-1
scanf("%d",&search);
if(iterativesearch(root,search))
cout<<search<<" is present in the BST";
else
cout<<search<<" is not present in the BST";
return 0;
}

93/95
#include<iostream>
#include<cstdlib>
using namespace std;
struct node
{
int data;
struct node*left;
struct node*right;
};
struct node*root;
void append(int d)//3
{
struct node*newnode = (struct node*)malloc(sizeof(struct node));
struct node*temp = root;//6
newnode->data = d;//3
newnode->left = NULL;
newnode->right = NULL;
if(root == NULL)//6
{
root = newnode;//6
}
else
{
while(true)
{
if(d < temp->data)
{
if(temp->left != NULL)
{
temp = temp->left;
}
else
{
temp->left = newnode;//6->3
break;
}
}else
{
if(temp->right != NULL)
{
temp = temp->right;
}else
{
temp->right = newnode;
break;
}
}
}
}
}
bool iterativesearch(struct node*root,int key)
{
while(root != NULL)//10
{
if(key > root->data)
{

94/95
 root = root->right;//10
}
else if(key < root->data)
{
root = root->left;
}
else
return true;
}
return false;
}
int main()
{
int d,search;
do
{
cin>>d;//3
if(d > 0)
append(d);
}while(d != -1);//-1
cin>>search;
if(iterativesearch(root,search))
cout<<search<<" is present in the BST";
else
cout<<search<<" is not present in the BST";
return 0;
}

95/95