Day- 03
Solution 1-
Q1. Given a Binary Search Tree (BST), find the Kth smallest element in
the tree.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int val) {
data = val;
left = right = nullptr;
};
void inorder(Node* root, int& k, int& result) {
if (root == nullptr) return;
inorder(root->left, k, result);
k--; // Decrement k for each visited node
if (k == 0) {
result = root->data;
return;
inorder(root->right, k, result);
int kthSmallest(Node* root, int k) {
int result = -1;
inorder(root, k, result);
return result;
int main() {
/*
/\
3 7
/\ \
2 4 8
*/
Node* root = new Node(5);
root->left = new Node(3);
root->right = new Node(7);
root->left->left = new Node(2);
root->left->right = new Node(4);
root->right->right = new Node(8);
int k = 3;
cout << "The " << k << "rd smallest element is: " << kthSmallest(root, k) << endl;
return 0;
Solution 2-
Q2. You are given a directed weighted graph where the weights on the
edges change over time. Each edge (u, v) has an associated weight
function f(t), where t is the time at which the edge is traversed. You need
to find the shortest path from a given source node to a destination node at
a specified time T.
The edge weight changes periodically (e.g., it could represent traffic
conditions or road congestion that varies over time). You need to
calculate the shortest path from the source to the destination at a specific
time, considering the dynamic nature of the edge weights. Write a
program in c/c++ to perform said method.
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <limits>
using namespace std;
struct Edge {
int to;
double baseWeight;
double period;
};
struct NodeState {
int node;
double time;
bool operator>(const NodeState& other) const {
return time > other.time;
};
double f(double t, double baseWeight, double period) {
// Example dynamic function: weight = base + sin(t) mod period
return baseWeight + fmod(sin(t), period);
vector<double> dynamicDijkstra(int n, vector<vector<Edge>>& graph, int src, double startTime) {
vector<double> dist(n, numeric_limits<double>::infinity());
priority_queue<NodeState, vector<NodeState>, greater<NodeState>> pq;
dist[src] = startTime;
pq.push({src, startTime});
while (!pq.empty()) {
NodeState current = pq.top(); pq.pop();
int u = current.node;
double currentTime = current.time;
if (currentTime > dist[u]) continue;
for (Edge& e : graph[u]) {
double dynamicWeight = f(currentTime, e.baseWeight, e.period);
double arrivalTime = currentTime + dynamicWeight;
if (arrivalTime < dist[e.to]) {
dist[e.to] = arrivalTime;
pq.push({e.to, arrivalTime});
return dist;
int main() {
int n = 4; // Number of nodes
vector<vector<Edge>> graph(n);
// Directed edges with base weight and period
graph[0].push_back({1, 2.0, 3.0});
graph[1].push_back({2, 1.5, 2.0});
graph[2].push_back({3, 2.5, 4.0});
graph[0].push_back({2, 4.0, 1.5});
graph[1].push_back({3, 6.0, 3.5});
int src = 0, dest = 3;
double startTime = 2.0;
vector<double> result = dynamicDijkstra(n, graph, src, startTime);
if (result[dest] == numeric_limits<double>::infinity())
cout << "No path exists from source to destination.\n";
else
cout << "Shortest time from " << src << " to " << dest << " starting at time " << startTime
<< " is: " << result[dest] << endl;
return 0;
