Find the Kth Smallest Element in a Binary Search Tree (BST) – C++

Introduction

In this guide, we will write a C++ program to find the kth smallest element in a Binary Search Tree (BST).
A BST is a binary tree where each node follows the following properties:

• All nodes in the left subtree of a node are smaller than the node’s value.
• All nodes in the right subtree of a node are larger than the node’s value.

The idea here is to perform an in-order traversal (which visits nodes in ascending order in a BST) and count the elements as we traverse to find the kth smallest element.

Program Structure

The program has the following structure:

1. Define a TreeNode structure representing each node in the BST.
2. Write a recursive inOrderTraversal function to traverse the BST in in-order fashion.
3. In the traversal function, maintain a count and stop traversal when the kth smallest element is found.
4. Use the kthSmallest function to initiate the traversal and return the kth smallest element.

Code Implementation

// C++ program to find the kth smallest element in a BST

#include <iostream>
using namespace std;

// Define the structure of a tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    // Constructor to initialize the tree node
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Helper function to perform in-order traversal and find the kth smallest element
void inOrderTraversal(TreeNode* root, int& k, int& result) {
    if (!root) return;  // Base case: if the root is NULL, return

    // Traverse the left subtree
    inOrderTraversal(root->left, k, result);

    // Decrement k when visiting the node
    k--;

    // If k becomes zero, we have found the kth smallest element
    if (k == 0) {
        result = root->val;
        return;
    }

    // Traverse the right subtree
    inOrderTraversal(root->right, k, result);
}

// Function to find the kth smallest element in the BST
int kthSmallest(TreeNode* root, int k) {
    int result = -1;  // To store the result
    inOrderTraversal(root, k, result);  // Start in-order traversal
    return result;  // Return the kth smallest element
}

// Helper function to insert a new node into the BST
TreeNode* insert(TreeNode* node, int val) {
    if (node == NULL) return new TreeNode(val);  // If the tree is empty, create a new node

    // Otherwise, recursively insert the value into the left or right subtree
    if (val < node->val)
        node->left = insert(node->left, val);
    else
        node->right = insert(node->right, val);

    return node;
}

int main() {
    /* Sample BST:
              5
            /   \
           3     7
          / \   / \
         2   4 6   8
    */

    // Creating the BST
    TreeNode* root = NULL;
    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 7);
    root = insert(root, 2);
    root = insert(root, 4);
    root = insert(root, 6);
    root = insert(root, 8);

    // Finding the kth smallest element
    int k = 3;  // For example, find the 3rd smallest element
    int result = kthSmallest(root, k);

    // Output the result
    cout << "The " << k << "rd smallest element in the BST is: " << result << endl;

    return 0;
}

Explanation

Let’s break down the program:

1. TreeNode structure: This structure represents a node in the binary search tree. Each node stores a value val and pointers to its left and right children.
2. inOrderTraversal function: This function performs an in-order traversal of the BST. It visits the left subtree, then the current node, and finally the right subtree. By decrementing the k variable and checking if it reaches zero, we find the kth smallest element.
3. kthSmallest function: This function calls the in-order traversal function and returns the kth smallest element. The variable result holds the final value.
4. insert function: This helper function is used to insert nodes into the BST by comparing values and placing the new node in the appropriate subtree (left for smaller values, right for larger values).

Sample Output

If you run the above program, for the sample BST and k = 3, the output will be:

The 3rd smallest element in the BST is: 4

Conclusion

The in-order traversal of a Binary Search Tree allows us to visit the elements in ascending order. By counting the number of elements as we traverse, we can easily find the kth smallest element in the BST. This method is efficient with a time complexity of O(N), where N is the number of nodes in the tree, and space complexity of O(H), where H is the height of the tree.