Kth Smallest Element in BST in DSA C++ - Build from Scratch

Kth Smallest Element in BST

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers in a way that smaller numbers go to the left and larger numbers go to the right. You want to find the kth smallest number in this tree, which means the number that would appear in position k if you listed all numbers in order.

🎯 Goal: Build a program that creates a BST, sets a value for k, finds the kth smallest element in the BST using an in-order traversal, and prints the result.

📋 What You'll Learn

Create a BST with the exact nodes given

Set an integer variable k to specify which smallest element to find

Implement an in-order traversal to find the kth smallest element

Print the kth smallest element found

💡 Why This Matters

🌍 Real World

Finding the kth smallest element in a BST is useful in databases and search engines where you want to quickly find ranked data like the 3rd cheapest product or 5th highest score.

💼 Career

Understanding BST traversal and selection algorithms is important for software engineers working on data retrieval, optimization, and systems that require efficient searching and sorting.

1

Create the BST nodes

Create a struct called Node with an integer val, and two pointers left and right. Then create the BST with these exact nodes and connections:
root with value 5,
root's left child with value 3,
root's right child with value 7,
left child's left child with value 2,
left child's right child with value 4,
right child's left child with value 6,
right child's right child with value 8.

DSA C++

// Define struct Node
// Create nodes and connect them as described
// Your code here

Hint

Start by defining the Node struct with a constructor. Then create the root node and add children exactly as described.

2

Set the value of k

Create an integer variable called k and set it to 3. This means you want to find the 3rd smallest element in the BST.

DSA C++

#include 
using namespace std;

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);

// Set k to 3
// Your code here

Hint

Just create an integer variable named k and assign it the value 3.

3

Implement in-order traversal to find kth smallest

Write a function called kthSmallest that takes Node* root and int k as parameters and returns the kth smallest integer in the BST. Use an in-order traversal (left, root, right) and a counter to find the kth smallest element.

DSA C++

#include 
using namespace std;

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);

int k = 3;

// Write kthSmallest function below
// Your code here

Hint

Use a helper function inorder to visit nodes in order. Keep a counter and when it reaches k, save the node's value.

4

Print the kth smallest element

Use cout to print the result of calling kthSmallest(root, k). This will show the kth smallest element in the BST.

DSA C++

#include 
using namespace std;

// Previous code above

// Print the kth smallest element below
// Your code here

Hint

Call kthSmallest(root, k) and print the returned value using cout.