Kth Smallest Element in BST in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inorder Traversal for Kth Smallest

What is the output of the inorder traversal of this BST before finding the 3rd smallest element?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

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->left = new Node(6);
root->right->right = new Node(8);

void inorder(Node* node, vector<int>& res) {
    if (!node) return;
    inorder(node->left, res);
    res.push_back(node->val);
    inorder(node->right, res);
}

vector<int> result;
inorder(root, result);
for (int v : result) cout << v << " ";

A 2 3 4 5 6 7 8

B 8 7 6 5 4 3 2

C 5 3 2 4 7 6 8

D 3 2 4 5 7 6 8

💡 Hint

Inorder traversal of BST visits nodes in ascending order.

Inorder traversal visits left subtree, then node, then right subtree. For BST, this gives sorted order.

❓ Predict Output

intermediate

Output of Kth Smallest Element Function

What is the output of the function that finds the 4th smallest element in the BST below?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

int count = 0;
int kthSmallest = -1;

void inorderKth(Node* node, int k) {
    if (!node || count >= k) return;
    inorderKth(node->left, k);
    count++;
    if (count == k) {
        kthSmallest = node->val;
        return;
    }
    inorderKth(node->right, k);
}

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->left = new Node(6);
root->right->right = new Node(8);

inorderKth(root, 4);
cout << kthSmallest;

A 3

B 5

C 6

D 4

💡 Hint

Count nodes visited in ascending order until reaching k.

The 4th smallest element in sorted order [2,3,4,5,6,7,8] is 5.

🔧 Debug

advanced

Identify the Bug in Kth Smallest Element Code

What error will this code produce when trying to find the 2nd smallest element?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

int count = 0;
int kthSmallest = -1;

void inorderKth(Node* node, int k) {
    if (!node) return;
    inorderKth(node->left, k);
    count++;
    if (count == k) {
        kthSmallest = node->val;
    }
    inorderKth(node->right, k);
}

Node* root = new Node(3);
root->left = new Node(1);
root->right = new Node(4);
root->left->right = new Node(2);

inorderKth(root, 2);
cout << kthSmallest;

A Runs infinitely

B Outputs 2 correctly

C Outputs -1 (default value)

D Outputs 3 instead of 2

💡 Hint

Check if traversal stops after finding kth element.

The code does not stop traversal after finding kth element, so kthSmallest gets overwritten by later nodes.

🧠 Conceptual

advanced

Time Complexity of Kth Smallest Element in BST

What is the average time complexity to find the kth smallest element in a balanced BST using inorder traversal?

A O(k)

B O(n)

C O(log n)

D O(k log n)

💡 Hint

Inorder traversal visits nodes in ascending order until kth is found.

We only need to visit k nodes in inorder traversal, so average time is O(k).

🚀 Application

expert

Result of Kth Smallest Element After Tree Modification

Given the BST below, after inserting a new node with value 1, what is the 3rd smallest element?

DSA C++

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

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->left = new Node(6);
root->right->right = new Node(8);

// Insert new node with value 1
root->left->left->left = new Node(1);

int count = 0;
int kthSmallest = -1;

void inorderKth(Node* node, int k) {
    if (!node || count >= k) return;
    inorderKth(node->left, k);
    count++;
    if (count == k) {
        kthSmallest = node->val;
        return;
    }
    inorderKth(node->right, k);
}

inorderKth(root, 3);
cout << kthSmallest;

A 1

B 3

C 2

D 4

💡 Hint

Remember to include the new node in the sorted order.

After insertion, inorder traversal is [1,2,3,4,5,6,7,8]. The 3rd smallest is 2.