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, like finding the 3rd smallest number in a list of numbers.

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

📋 What You'll Learn

Create a BST with the exact nodes and structure given

Create an integer variable k with the exact value given

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

Print the kth smallest element exactly as specified

💡 Why This Matters

🌍 Real World

Finding the kth smallest element is useful in databases, search engines, and ranking systems where you want to find a specific order statistic quickly.

💼 Career

Understanding BSTs and order statistics is important for software engineers working on efficient data retrieval, optimization, and algorithm design.

1

Create the BST nodes

Create the BST nodes exactly as follows: a root node with value 5, a left child with value 3, a right child with value 7, the left child of node 3 with value 2, and the right child of node 3 with value 4. Use the struct Node and create pointers named root, node3, node7, node2, and node4 accordingly.

DSA C

#include 
#include 

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

int main() {

    // Create BST nodes here

    return 0;
}

Hint

Use malloc to create each node and set their data values. Connect the nodes by setting the left and right pointers.

2

Set the value of k

Create an integer variable called k and set it to 3 inside the main function, after creating the BST nodes.

DSA C

#include 
#include 

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

int main() {
    struct Node* root = (struct Node*)malloc(sizeof(struct Node));
    root->data = 5;
    struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));
    node3->data = 3;
    struct Node* node7 = (struct Node*)malloc(sizeof(struct Node));
    node7->data = 7;
    struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
    node2->data = 2;
    struct Node* node4 = (struct Node*)malloc(sizeof(struct Node));
    node4->data = 4;

    root->left = node3;
    root->right = node7;
    node3->left = node2;
    node3->right = node4;
    node7->left = NULL;
    node7->right = NULL;
    node2->left = NULL;
    node2->right = NULL;
    node4->left = NULL;
    node4->right = NULL;

    // Create variable k and set it to 3

    return 0;
}

Hint

Simply declare int k = 3; inside main after the nodes are created.

3

Implement the kth smallest element function

Write a function called kthSmallest that takes a pointer to Node, a pointer to an integer k, and a pointer to an integer result. Use in-order traversal to find the kth smallest element in the BST. Decrease *k each time you visit a node. When *k reaches zero, set *result to the current node's data. Call this function from main with root, address of k, and address of an integer result variable initialized to -1.

DSA C

#include 
#include 

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Write kthSmallest function here

int main() {
    struct Node* root = (struct Node*)malloc(sizeof(struct Node));
    root->data = 5;
    struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));
    node3->data = 3;
    struct Node* node7 = (struct Node*)malloc(sizeof(struct Node));
    node7->data = 7;
    struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
    node2->data = 2;
    struct Node* node4 = (struct Node*)malloc(sizeof(struct Node));
    node4->data = 4;

    root->left = node3;
    root->right = node7;
    node3->left = node2;
    node3->right = node4;
    node7->left = NULL;
    node7->right = NULL;
    node2->left = NULL;
    node2->right = NULL;
    node4->left = NULL;
    node4->right = NULL;

    int k = 3;

    // Call kthSmallest function here

    return 0;
}

Hint

Use in-order traversal: visit left child, then current node, then right child. Decrease *k when visiting a node. When *k is zero, store the node's data in *result.

4

Print the kth smallest element

Print the value of the variable result using printf exactly as: printf("%d\n", result); inside the main function after calling kthSmallest.

DSA C

#include 
#include 

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

void kthSmallest(struct Node* root, int* k, int* result) {
    if (root == NULL || *k == 0) {
        return;
    }
    kthSmallest(root->left, k, result);
    if (*k == 0) {
        return;
    }
    (*k)--;
    if (*k == 0) {
        *result = root->data;
        return;
    }
    kthSmallest(root->right, k, result);
}

int main() {
    struct Node* root = (struct Node*)malloc(sizeof(struct Node));
    root->data = 5;
    struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));
    node3->data = 3;
    struct Node* node7 = (struct Node*)malloc(sizeof(struct Node));
    node7->data = 7;
    struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
    node2->data = 2;
    struct Node* node4 = (struct Node*)malloc(sizeof(struct Node));
    node4->data = 4;

    root->left = node3;
    root->right = node7;
    node3->left = node2;
    node3->right = node4;
    node7->left = NULL;
    node7->right = NULL;
    node2->left = NULL;
    node2->right = NULL;
    node4->left = NULL;
    node4->right = NULL;

    int k = 3;
    int result = -1;
    kthSmallest(root, &k, &result);

    // Print the result

    return 0;
}

Hint

Use printf("%d\n", result); to print the kth smallest element after calling kthSmallest.

Practice

1. What does the term kth smallest element in a BST mean?

easy

A. The element that appears in the kth position when BST elements are sorted in ascending order

B. The element with the kth largest value in the BST

C. The element at the kth level of the BST

D. The element with the kth highest frequency in the BST

Solution

1. Step 1: Understand BST property

   A Binary Search Tree (BST) stores elements so that left subtree has smaller values and right subtree has larger values.

2. Step 2: Define kth smallest element

   The kth smallest element is the one that appears in the kth position when all elements are sorted in ascending order.

3. Final Answer:

   The element that appears in the kth position when BST elements are sorted in ascending order -> Option A

4. Quick Check:

   kth smallest = kth in sorted order [OK]

Hint: Think of inorder traversal to get sorted order [OK]

Common Mistakes:

• Confusing kth smallest with kth largest
• Thinking kth smallest means kth level node
• Assuming frequency matters

2. Which of the following C function signatures is correct to find the kth smallest element in a BST node structure struct Node?

easy

A. void kthSmallest(int root, int k);

B. int kthSmallest(struct Node root, int k);

C. int kthSmallest(struct Node* root, int k);

D. int kthSmallest(struct Node* root);

Solution

1. Step 1: Understand function parameters

   The function needs the root pointer to the BST and the integer k to find kth smallest.

2. Step 2: Check parameter types

   Passing struct Node* for root and int for k is correct. Return type should be int for the element value.

3. Final Answer:

   int kthSmallest(struct Node* root, int k); -> Option C

4. Quick Check:

   Correct signature includes pointer and k parameter [OK]

Hint: Use pointer for tree root and int for k [OK]

Common Mistakes:

• Passing root by value instead of pointer
• Missing k parameter
• Wrong return type or missing return

3. Given the BST below and k = 3, what is the output of the function kthSmallest(root, 3)?

      5
     / \
    3   7
   / \   \
  2   4   8

medium

A. 5

B. 4

C. 3

D. 7

Solution

1. Step 1: Perform inorder traversal

   Inorder traversal of BST visits nodes in ascending order: 2, 3, 4, 5, 7, 8.

2. Step 2: Identify 3rd element in traversal

   The 3rd element is 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Inorder 3rd element = 4 [OK]

Hint: Inorder traversal gives sorted order; pick kth element [OK]

Common Mistakes:

• Counting nodes incorrectly in traversal
• Confusing preorder or postorder with inorder
• Choosing root or other node instead of kth

4. Consider this buggy C code snippet to find kth smallest element in BST:

int count = 0;
int kthSmallest(struct Node* root, int k) {
    if (!root) return -1;
    int left = kthSmallest(root->left, k);
    if (left != -1) return left;
    count++;
    if (count == k) return root->data;
    return kthSmallest(root->right, k);
}

What is the main issue with this code?

medium

A. Global variable 'count' causes incorrect results on multiple calls

B. Function does not handle empty tree

C. Returns -1 for valid kth element

D. Does not traverse right subtree

Solution

1. Step 1: Analyze use of 'count'

   The variable 'count' is global and not reset between calls, causing wrong counts if function called multiple times.

2. Step 2: Understand impact on results

   Because 'count' is not reset, subsequent calls may return wrong kth smallest element or fail.

3. Final Answer:

   Global variable 'count' causes incorrect results on multiple calls -> Option A

4. Quick Check:

   Global count not reset breaks repeated calls [OK]

Hint: Avoid global counters; pass as function argument [OK]

Common Mistakes:

• Ignoring global variable side effects
• Assuming function works for multiple calls
• Not resetting count before each call

5. You have a BST with nodes containing duplicate values. How would you modify the standard kth smallest element algorithm to correctly find the kth smallest unique element?

hard

A. Use preorder traversal instead of inorder

B. Count all nodes including duplicates normally

C. Remove duplicates from BST before traversal

D. Use inorder traversal and skip duplicates by comparing with previous visited value

Solution

1. Step 1: Understand duplicates in BST

   Duplicates appear as multiple nodes with same value; inorder traversal visits them in sorted order including duplicates.

2. Step 2: Modify traversal to skip duplicates

   Track previous visited value during inorder traversal; only increment count when current value differs from previous.

3. Step 3: Find kth unique element

   Increment count only for unique values; when count equals k, return current node's value.

4. Final Answer:

   Use inorder traversal and skip duplicates by comparing with previous visited value -> Option D

5. Quick Check:

   Skip duplicates by comparing previous value [OK]

Hint: Track previous value to count unique elements [OK]

Common Mistakes:

• Counting duplicates as separate elements
• Using preorder traversal which is not sorted
• Trying to remove duplicates instead of skipping