Kth Smallest Element in a BST - Practice Coding Problems

Kth Smallest Element in a BST - Problem

Given the root of a binary search tree and an integer k, return the k-th smallest value (1-indexed) of all the values of the nodes in the tree.

A binary search tree (BST) is a tree where for every node, all values in the left subtree are smaller than the node's value, and all values in the right subtree are greater than the node's value.

Follow up: If the BST is modified frequently (insertions and deletions), how would you optimize the solution?

Input & Output

Example 1 — Basic BST

$ Input: root = [3,1,4,null,2], k = 1

› Output: 1

💡 Note: The BST has values [1,2,3,4] in sorted order. The 1st smallest value is 1.

Example 2 — Find 3rd Smallest

$ Input: root = [5,3,6,2,4,null,null,1], k = 3

› Output: 3

💡 Note: The sorted values are [1,2,3,4,5,6]. The 3rd smallest value is 3.

Example 3 — Single Node

$ Input: root = [1], k = 1

› Output: 1

💡 Note: Only one node exists, so the 1st smallest is 1.

Constraints

The number of nodes in the tree is n.
1 ≤ k ≤ n ≤ 10⁴
0 ≤ Node.val ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

BST with nodes [3,1,4,null,2] and k=1

Process

In-order traversal gives sorted sequence: 1,2,3,4

Output

Return the k-th (1st) smallest element: 1

Key Takeaway

🎯 Key Insight: In-order traversal of BST naturally visits nodes in ascending order

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that in-order traversal of a BST visits nodes in sorted order. We can use this property to find the k-th smallest element efficiently by counting nodes during traversal and stopping when we reach the k-th node. Best approach is In-Order Traversal with Time: O(h + k), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Collect All Values Then Sort	O(n log n)	O(n)	Traverse entire tree, collect all values, sort them, return k-th element
In-Order Traversal with Counter	O(h + k)	O(h)	Use in-order traversal (left-root-right) which visits BST nodes in sorted order, count until k-th element

Collect All Values Then Sort — Algorithm Steps

Step 1: Traverse entire tree and collect all values
Step 2: Sort the collected values
Step 3: Return the k-th element (index k-1)

Visualization

Tap to expand

Step-by-Step Walkthrough

Traverse

Collect all node values: [3,1,4,2]

Sort

Sort the values: [1,2,3,4]

Result

Return k-th element (k=1): value 1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

void traverse(struct TreeNode* node, int* values, int* count) {
    if (!node) return;
    values[(*count)++] = node->val;
    traverse(node->left, values, count);
    traverse(node->right, values, count);
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(struct TreeNode* root, int k) {
    int values[10000];
    int count = 0;
    traverse(root, values, &count);
    qsort(values, count, sizeof(int), compare);
    return values[k-1];
}

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

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

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

O(n) to traverse tree + O(n log n) to sort values

⚡ Linearithmic

Space Complexity

O(n)

Array stores all n node values

⚡ Linearithmic Space

255.0K Views

High Frequency

~15 min Avg. Time

8.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Collect All Values Then Sort — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler