Scribd
Upload
7 views

DSA Lab Assignment 10 D0

The document outlines a lab assignment for a DSA course at IIT Dharwad, focusing on binary trees. It includes instructions for setting up directories and naming conventions for code submissions, as well as three programming tasks: checking if a binary tree is a binary search tree (BST), implementing a BST with insertion, deletion, and searching functions, and calculating the height of a binary tree. Each task is accompanied by example code and test cases to validate the implementations.

Uploaded by

ch23bt004
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views

DSA Lab Assignment 10 D0

The document outlines a lab assignment for a DSA course at IIT Dharwad, focusing on binary trees. It includes instructions for setting up directories and naming conventions for code submissions, as well as three programming tasks: checking if a binary tree is a binary search tree (BST), implementing a BST with insertion, deletion, and searching functions, and calculating the height of a binary tree. Each task is accompanied by example code and test cases to validate the implementations.

Uploaded by

ch23bt004
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

DSA Lab – 10

Binary Tree

Batch – D0

(March, 2024)

DEPARTMENT OF COMPUTER SCIENCE ENGINEERING


INDIAN INSTITUTE OF TECHNOLOGY DHARWAD
March, 2024
General Instructions
Before you start programming:

Open the terminal. Using suitable commands -

1. Please do not edit the main function.

2. Create a directory named “roll number” in the current directory.

3. Create another directory named “LAB number” within the roll number directory.

4. Within the “LAB_number” directory place your files. Follow the naming convention as
“RollNumber_PracticeQuestionNumber.c” (for example 23200100_p1.c) for practice
questions. Follow the naming convention as “RollNumber_TestQuestionNumber.c” (for
example 23200100 test1.c) for test questions.

After you complete programming and before leaving the lab:

1. Ensure your assigned TA has marked your attendance.

2. Ensure your assigned TA has checked your practice question and test question solutions
and you are evaluated for the same.

3. Ensure to upload your folder on Moodle after evaluation.


1. Write a C program to check whether a binary tree is a binary search tree (BST) or not.
Implement a function isBST() that takes the root of the tree as input and returns true if it is a
BST, and false otherwise. Test your program by creating both valid and invalid binary trees,
and verify the correctness of the output.

[6 Points]

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>

// Binary Tree Node Structure


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

// Function to create a new node


struct TreeNode* createNode(int data) {
//Your code here
}

// Function to check if a binary tree is a BST.


bool isBST(struct TreeNode* root) {
//Your code here
}

Test cases:

int main() {
// Test case 1: Valid BST
struct TreeNode* root1 = createNode(5);
root1->left = createNode(3);
root1->right = createNode(7);
root1->left->left = createNode(2);
root1->left->right = createNode(4);
printf("Test Case 1: %s\n", isBST(root1) ? "Valid BST" : "Not a
BST");

// Test case 2: Invalid BST


struct TreeNode* root2 = createNode(5);
root2->left = createNode(3);
root2->right = createNode(7);
root2->left->left = createNode(6); // Violating BST property
root2->left->right = createNode(4);
printf("Test Case 2: %s\n", isBST(root2) ? "Valid BST" : "Not a
BST");

// Test case 3: Empty tree


struct TreeNode* root3 = NULL;
printf("Test Case 3: %s\n", isBST(root3) ? "Valid BST" : "Not a
BST");

// Test case 4: Single node tree


struct TreeNode* root4 = createNode(10);
printf("Test Case 4: %s\n", isBST(root4) ? "Valid BST" : "Not a
BST");

// Test case 5: Binary tree with duplicate values


struct TreeNode* root5 = createNode(10);
root5->left = createNode(5);
root5->right = createNode(15);
root5->left->left = createNode(5); // Duplicate value
printf("Test Case 5: %s\n", isBST(root5) ? "Valid BST" : "Not a
BST");

return 0;
}

2. Write a C program to implement a binary search tree (BST). Include functions for insertion,
deletion, and searching for a key in the BST. Use in-order traversal to print the elements of
the tree.
[6 Points]

#include <stdio.h>
#include <stdlib.h>

// Binary Search Tree Node Structure


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

// Function to create a new node


struct TreeNode* createNode(int data) {
//Your code here
}

// Function to insert a key into the BST


struct TreeNode* insert(struct TreeNode* root, int key) {
//Your code here
}

// Function to perform inorder traversal


void inorder(struct TreeNode* root) {
//Your code here
}

// Function to search for a key in the BST


struct TreeNode* search(struct TreeNode* root, int key) {
//Your code here
}

// Function to delete a key from the BST


struct TreeNode* deleteNode(struct TreeNode* root, int key) {
//Your code here
}

Test cases:

int main() {
struct TreeNode* root = NULL;

// Test Case 1: Insertion


root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printf("Inorder traversal after insertion: ");
inorder(root);
printf("\n");
// Test Case 2: Search
int keyToSearch = 40;
struct TreeNode* searchResult = search(root, keyToSearch);
if (searchResult != NULL)
printf("%d found in the tree\n", keyToSearch);
else
printf("%d not found in the tree\n", keyToSearch);

// Test Case 3: Deletion


int keyToDelete = 30;
root = deleteNode(root, keyToDelete);
printf("Inorder traversal after deletion of %d: ", keyToDelete);
inorder(root);
printf("\n");

// Test Case 4: Deleting non-existent key


int nonExistentKey = 100;
root = deleteNode(root, nonExistentKey);
printf("Inorder traversal after attempting to delete %d (non-existent): ", nonExistentKey);
inorder(root);
printf("\n");

// Test Case 5: Deleting root


root = deleteNode(root, 50);
printf("Inorder traversal after deletion of root: ");
inorder(root);
printf("\n");

return 0;
}
3. Implement a function in C to find the height of a binary tree. The height of a binary tree is the
maximum distance from the root node to any leaf node. Test your function by creating multiple bi-
nary trees with varying structures and sizes, and verify that the height is calculated correctly for each
tree.
[8 Points]

#include <stdio.h>
#include <stdlib.h>

// Binary Tree Node Structure


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

// Function to create a new node


struct TreeNode* createNode(int data) {
//Your code here
}

// Function to find the height of a binary tree


int height(struct TreeNode* root) {
//Your code here
}

Test cases:

int main() {
struct TreeNode* root1 = createNode(1);
root1->left = createNode(2);
root1->right = createNode(3);
root1->left->left = createNode(4);
root1->left->right = createNode(5);
root1->right->left = createNode(6);
root1->right->right = createNode(7);
printf("Height of Binary Tree 1: %d\n", height(root1));

struct TreeNode* root2 = createNode(1);


root2->left = createNode(2);
root2->left->left = createNode(3);
root2->left->left->left = createNode(4);
root2->left->left->left->left = createNode(5);
printf("Height of Binary Tree 2: %d\n", height(root2));

struct TreeNode* root3 = createNode(1);


root3->left = createNode(2);
root3->right = createNode(3);
root3->right->left = createNode(4);
root3->right->left->right = createNode(5);
root3->right->left->right->left = createNode(6);
printf("Height of Binary Tree 3: %d\n", height(root3));

struct TreeNode* root4 = createNode(1);


root4->left = createNode(2);
root4->right = createNode(3);
printf("Height of Binary Tree 4: %d\n", height(root4));

struct TreeNode* root5 = NULL;


printf("Height of Binary Tree 5: %d\n", height(root5));

return 0;
}

You might also like