Find the kth Smallest Element in a BST - Visualization

Binary Search Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

Given the root of a Binary Search Tree (BST) and an integer k, return the kth smallest value among all the nodes in the BST. The BST property ensures that the left subtree contains only nodes with values less than the root, and the right subtree only nodes with values greater than the root.

You can assume that 1 ≤ k ≤ N, where N is the number of nodes in the tree.

Examples❯

Input Tree k Output Description
[5, 3, 7, 2, 4, 6, 8]
3 4 In-order traversal gives [2, 3, 4, 5, 6, 7, 8], so 3rd smallest is 4
[10, 5, 15, 3, 7, null, 18]
4 10 In-order: [3, 5, 7, 10, 15, 18]; 4th element is 10
[20, 8, 22, 4, 12, null, null, null, null, 10, 14]
5 14 In-order: [4, 8, 10, 12, 14, 20, 22]; 5th element is 14
[3, 1, 4, null, 2]
1 1 In-order: [1, 2, 3, 4]; 1st element is 1
[2, 1, 3]
2 2 In-order: [1, 2, 3]; 2nd element is 2
[1]
1 1 Single node is the only (and thus 1st) element in-order

Solution❯

Understanding the Problem

We are given a Binary Search Tree (BST), and we are asked to find the kth smallest element in it. A Binary Search Tree has the special property that for any given node, all elements in its left subtree are smaller, and all elements in its right subtree are larger.

This means that if we perform an in-order traversal of the BST (visit left → root → right), we will visit the nodes in ascending order. By keeping count as we traverse, we can return the kth node visited, which will be the kth smallest element.

Step-by-Step Solution with Example

step 1: Choose a sample BST and the value of k

Let’s take the following BST:


        5
       /       3   7
     /        2   4   8

Suppose k = 3. We want to find the 3rd smallest element.

step 2: Perform in-order traversal (left → root → right)

During in-order traversal, we visit nodes in this order:

2 → 3 → 4 → 5 → 7 → 8

We count as we go. The 3rd element visited is 4.

step 3: Implement in-order traversal with a counter

As we recursively traverse, we pass a counter to track how many nodes we have visited. Once the counter equals k, we stop and return that node’s value.

step 4: Handle base cases

If the current node is null or we’ve already found the result, we simply return. This prevents unnecessary traversal once our answer is found.

step 5: Return the result

Once we reach the kth node, we store the value and return it. This value is our answer.

Edge Cases

Empty Tree

If the tree is null, there is no kth smallest element to find. In this case, we should return None or raise an error depending on requirements.

k is larger than total number of nodes

For example, if the tree has 4 nodes and k = 6, we cannot find the 6th smallest. We should check this condition and return an appropriate message or exception.

k is 1 or equal to total nodes

When k = 1, we are looking for the smallest element — the leftmost node. When k equals total number of nodes, we are looking for the largest — the rightmost node. The algorithm still works but make sure traversal reaches these nodes correctly.

Finally

This problem is a classic example of leveraging the properties of BSTs. Using in-order traversal is both natural and efficient for this task. For beginners, it's important to understand how traversal order affects the result. Always consider special scenarios like empty trees or out-of-bound values of k to build a robust solution.

With this approach, you're not just solving the problem — you're developing a strong grasp of tree traversal techniques.

Algorithm Steps❯

  1. Given a binary search tree (BST) and an integer k.
  2. Perform an in-order traversal of the BST, which visits nodes in ascending order.
  3. Keep a counter to track the number of nodes visited.
  4. When the counter equals k, record the current node's value as the kth smallest element.
  5. Return the recorded value as the result.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

void inorder(TreeNode* root, int k, int* count, int* result) {
    if (!root) return;
    inorder(root->left, k, count, result);
    (*count)++;
    if (*count == k) {
        *result = root->val;
        return;
    }
    inorder(root->right, k, count, result);
}

int kthSmallest(TreeNode* root, int k) {
    int count = 0, result = -1;
    inorder(root, k, &count, &result);
    return result;
}

int main() {
    TreeNode* root = createNode(3);
    root->left = createNode(1);
    root->right = createNode(4);
    root->left->right = createNode(2);
    printf("%d\n", kthSmallest(root, 1));
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...