Scribd
Upload
8 views

DSA Lab Assignment 3

Uploaded by

k bishnu prasad patro (subham)
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
8 views

DSA Lab Assignment 3

Uploaded by

k bishnu prasad patro (subham)
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/ 6

DSA Lab Assignment 3

Ques 1:

Answer 1:

#include <stdio.h>

#include <stdlib.h>

// Definition for a binary tree node.

struct TreeNode {

int val;

struct TreeNode *left, *right;

};

// Function to create a new node

struct TreeNode* newNode(int value) {

struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));

node->val = value;

node->left = node->right = NULL;

return node;

// Function to find the LCA of two nodes in a BST

struct TreeNode* findLCA(struct TreeNode* root, int n1, int n2) {

// Base case: if the tree is empty

if (root == NULL) return NULL;

// If both n1 and n2 are smaller than root, LCA is in the left subtree

if (n1 < root->val && n2 < root->val) {

return findLCA(root->left, n1, n2);

}
// If both n1 and n2 are greater than root, LCA is in the right subtree

if (n1 > root->val && n2 > root->val) {

return findLCA(root->right, n1, n2);

// If one node is on the left and the other is on the right, root is the LCA

return root;

// Test cases

int main() {

// Creating the BST

struct TreeNode* root = newNode(8);

root->left = newNode(3);

root->right = newNode(12);

root->left->left = newNode(1);

root->left->right = newNode(6);

root->right->left = newNode(10);

root->right->right = newNode(14);

// Test Case 1: LCA of 10 and 14

struct TreeNode* lca1 = findLCA(root, 10, 14);

if (lca1 != NULL)

printf("LCA of 10 and 14: %d\n", lca1->val); // Expected output: 12

else

printf("LCA not found\n");

// Test Case 2: LCA of 8 and 14

struct TreeNode* lca2 = findLCA(root, 8, 14);

if (lca2 != NULL)

printf("LCA of 8 and 14: %d\n", lca2->val); // Expected output: 8


else

printf("LCA not found\n");

return 0;

Output:

Ques 2:

Answer 2:

#include <stdio.h>

#include <stdlib.h>

// Definition for a binary tree node.

struct TreeNode {

int val;

struct TreeNode *left, *right;

};
// Function to create a new node

struct TreeNode* newNode(int value) {

struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));

node->val = value;

node->left = node->right = NULL;

return node;

// Helper function for in-order traversal to find the k-th smallest element

void inOrderTraversal(struct TreeNode* root, int k, int* count, int* result) {

if (root == NULL || *count >= k) {

return;

// Traverse the left subtree

inOrderTraversal(root->left, k, count, result);

// Increment count, and check if the current node is the k-th smallest

(*count)++;

if (*count == k) {

*result = root->val;

return;

// Traverse the right subtree

inOrderTraversal(root->right, k, count, result);

// Function to find the k-th smallest element in the BST

int findKthSmallest(struct TreeNode* root, int k) {

int count = 0;
int result = -1; // Default value if k is out of bounds

inOrderTraversal(root, k, &count, &result);

return result;

// Sample test cases

int main() {

// Creating the BST

struct TreeNode* root = newNode(8);

root->left = newNode(3);

root->right = newNode(12);

root->left->left = newNode(1);

root->left->right = newNode(6);

root->right->left = newNode(10);

root->right->right = newNode(14);

// Test Case 1: Find the 3rd smallest element

int k = 3;

int result = findKthSmallest(root, k);

printf("The %d-th smallest element is: %d\n", k, result); // Expected output: 10

// Test Case 2: Find the 5th smallest element

k = 5;

result = findKthSmallest(root, k);

printf("The %d-th smallest element is: %d\n", k, result); // Expected output: 14

return 0;

Output:

You might also like