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:
