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 contains data, left (left child), and right (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.

By Aditya Bhuyan

I work as a cloud specialist. In addition to being an architect and SRE specialist, I work as a cloud engineer and developer. I have assisted my clients in converting their antiquated programmes into contemporary microservices that operate on various cloud computing platforms such as AWS, GCP, Azure, or VMware Tanzu, as well as orchestration systems such as Docker Swarm or Kubernetes. For over twenty years, I have been employed in the IT sector as a Java developer, J2EE architect, scrum master, and instructor. I write about Cloud Native and Cloud often. Bangalore, India is where my family and I call home. I maintain my physical and mental fitness by doing a lot of yoga and meditation.

Leave a Reply

Your email address will not be published. Required fields are marked *

error

Enjoy this blog? Please spread the word :)