Find the kth Smallest Element in a Binary Search Tree

Problem and examples

Given the root of a Binary Search Tree (BST) and an integer k, return the k^th 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.

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

Explore Find the kth Smallest Element in a BST

Load an example or enter your own input. Use the player controls to follow each change.

Understanding the Problem

We are given a Binary Search Tree (BST), and we are asked to find the k^th 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 k^th node visited, which will be the k^th 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 k^th 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 k^th 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.

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

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
    int count = 0;
    int result = -1;
public:
    int kthSmallest(TreeNode* root, int k) {
        inorder(root, k);
        return result;
    }
    void inorder(TreeNode* node, int k) {
        if (!node) return;
        inorder(node->left, k);
        count++;
        if (count == k) {
            result = node->val;
            return;
        }
        inorder(node->right, k);
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(1);
    root->right = new TreeNode(4);
    root->left->right = new TreeNode(2);
    Solution sol;
    cout << sol.kthSmallest(root, 1) << endl;
    return 0;
}

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def kthSmallest(self, root, k):
        self.count = 0
        self.result = None

        def inorder(node):
            if not node or self.result is not None:
                return
            inorder(node.left)
            self.count += 1
            if self.count == k:
                self.result = node.val
                return
            inorder(node.right)

        inorder(root)
        return self.result

# Example
if __name__ == '__main__':
    root = TreeNode(3, TreeNode(1, None, TreeNode(2)), TreeNode(4))
    sol = Solution()
    print(sol.kthSmallest(root, 1))

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Main {
    static int count = 0;
    static int result = -1;

    public static int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return result;
    }

    private static void inorder(TreeNode node, int k) {
        if (node == null) return;
        inorder(node.left, k);
        count++;
        if (count == k) {
            result = node.val;
            return;
        }
        inorder(node.right, k);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        System.out.println(kthSmallest(root, 1));
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function kthSmallest(root, k) {
    let count = 0, result = null;
    function inorder(node) {
        if (!node || result !== null) return;
        inorder(node.left);
        count++;
        if (count === k) {
            result = node.val;
            return;
        }
        inorder(node.right);
    }
    inorder(root);
    return result;
}

const root = new TreeNode(3, new TreeNode(1, null, new TreeNode(2)), new TreeNode(4));
console.log(kthSmallest(root, 1));

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

var count int
var result int

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

func inorder(node *TreeNode, k int) {
    if node == nil {
        return
    }
    inorder(node.Left, k)
    count++
    if count == k {
        result = node.Val
        return
    }
    inorder(node.Right, k)
}

func main() {
    root := &TreeNode{3, &TreeNode{1, nil, &TreeNode{2, nil, nil}}, &TreeNode{4, nil, nil}}
    fmt.Println(kthSmallest(root, 1))
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn inorder(node: &Option<Box<TreeNode>>, k: i32, count: &mut i32, result: &mut Option<i32>) {
    if let Some(n) = node {
        inorder(&n.left, k, count, result);
        *count += 1;
        if *count == k {
            *result = Some(n.val);
            return;
        }
        inorder(&n.right, k, count, result);
    }
}

fn kth_smallest(root: Option<Box<TreeNode>>, k: i32) -> i32 {
    let mut count = 0;
    let mut result = None;
    inorder(&root, k, &mut count, &mut result);
    result.unwrap()
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 3,
        left: Some(Box::new(TreeNode {
            val: 1,
            left: None,
            right: Some(Box::new(TreeNode::new(2)),)
        })),
        right: Some(Box::new(TreeNode::new(4)),)
    }));

    println!("{}", kth_smallest(root, 1));
}

Kotlin implementation

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    private var count = 0
    private var result = -1

    fun kthSmallest(root: TreeNode?, k: Int): Int {
        inorder(root, k)
        return result
    }

    private fun inorder(node: TreeNode?, k: Int) {
        if (node == null) return
        inorder(node.left, k)
        count++
        if (count == k) {
            result = node.`val`
            return
        }
        inorder(node.right, k)
    }
}

fun main() {
    val root = TreeNode(3)
    root.left = TreeNode(1)
    root.right = TreeNode(4)
    root.left!!.right = TreeNode(2)
    val sol = Solution()
    println(sol.kthSmallest(root, 1))
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

class Solution {
    var count = 0
    var result: Int?

    func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
        inorder(root, k)
        return result ?? -1
    }

    private func inorder(_ node: TreeNode?, _ k: Int) {
        guard let node = node else { return }
        inorder(node.left, k)
        count += 1
        if count == k {
            result = node.val
            return
        }
        inorder(node.right, k)
    }
}

let root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left?.right = TreeNode(2)
let sol = Solution()
print(sol.kthSmallest(root, 1))

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function kthSmallest(root: TreeNode | null, k: number): number {
    let count = 0;
    let result = -1;

    function inorder(node: TreeNode | null) {
        if (!node) return;
        inorder(node.left);
        count++;
        if (count === k) {
            result = node.val;
            return;
        }
        inorder(node.right);
    }

    inorder(root);
    return result;
}

const root = new TreeNode(3, new TreeNode(1, null, new TreeNode(2)), new TreeNode(4));
console.log(kthSmallest(root, 1));