This program uses an in-order traversal to find the kth smallest element in a Binary Search Tree (BST). The essence of in-order traversal is that it processes the BST nodes in ascending order, which is directly applicable for finding the kth smallest element.
Program Explanation
The structure of the program includes:
- Node Structure: Defines the structure of each node in the BST.
- Insert Function: Helps in building the BST by inserting nodes in a manner that maintains the BST properties.
- In-order Traversal Function: A recursive function that visits nodes in an in-order fashion to find the kth smallest element.
- Main Function: The entry point of the program, where the BST is constructed and the kth smallest element is found.
Program Code
// Include necessary headers
#include <stdio.h>
#include <stdlib.h>
// Define the structure for BST nodes
typedef struct node {
int data;
struct node* left;
struct node* right;
} Node;
// Function to create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// Function to insert a new node in the BST
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else
root->right = insert(root->right, data);
return root;
}
// Function to find the kth smallest element using in-order traversal
void kthSmallestUtil(Node* root, int k, int* count, int* result) {
if (root == NULL || *count >= k)
return;
// Traverse the left subtree
kthSmallestUtil(root->left, k, count, result);
// Increment count of visited nodes
if (++(*count) == k) {
*result = root->data;
return;
}
// Traverse the right subtree
kthSmallestUtil(root->right, k, count, result);
}
// Wrapper over kthSmallestUtil
int kthSmallest(Node* root, int k) {
int count = 0;
int result = -1; // To store the kth smallest element
kthSmallestUtil(root, k, &count, &result);
return result;
}
// Main function
int main() {
Node* root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 70);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 60);
root = insert(root, 80);
int k = 3;
printf("The %dth smallest element is %d\\n", k, kthSmallest(root, k));
return 0;
}
Key Points of the Program:
- Node Structure: Each
node
containsdata
,left
(left child), andright
(right child). - Insert Function: Inserts a new node into the BST maintaining the BST properties.
- In-order Traversal Function (
kthSmallestUtil
): This recursive function is critical for accessing the nodes in ascending order. It uses a counter to track the number of nodes processed until it reaches the kth node. - Wrapper Function (
kthSmallest
): Handles initial conditions and calls the utility function. - Main Function: Sets up the BST and finds the kth smallest element by calling the
kthSmallest
function.