Kth Smallest Element in a BST

Problem Statement

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

What to notice first

• In a BST, in-order traversal visits nodes in ascending sorted order.
• You can count as you traverse and stop at the kth node.
• No need to store all values; process on-the-fly.

Examples

Input	k	Output	Explanation
Tree: 3, 1→null, 1→2, 4	1	1	Sorted: [1, 2, 3, 4], 1st = 1
Tree: 3, 1→null, 1→2, 4	3	2	Sorted: [1, 2, 3, 4], 3rd = 2
Tree: 5, 3, 6	1	3	Sorted: [3, 5, 6], 1st = 3

Constraints

• The number of nodes in the tree is n.
• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^4

Real-World Applications

Where this pattern appears

• Percentile ranking — find the kth percentile student score in a sorted dataset.
• Leaderboard systems — retrieve the kth highest score efficiently.
• Data streaming — find the kth smallest event timestamp without storing all events.
• Statistical analysis — extract medians and quartiles from sorted data.

Complexity Comparison

Approach	Time	Space	Key Idea	Best When
In-Order DFS	O(n)	O(h)	Recursive in-order, count k nodes, return	General case — simple and elegant
Morris In-Order	O(n)	O(1)	Thread-based traversal, no recursion stack	Space-critical — embedded systems, interview edge case

Which approach should you learn first?

• Pick In-Order DFS as your primary solution.
• Learn Morris In-Order if you want to optimize space to O(1).

Most Common

In-Order DFS

O(n) time · O(h) space

Space-Optimized

Morris In-Order

O(n) time · O(1) space

Approach 1: In-Order DFS (Recommended)

★ Recommended

Recursively traverse the tree in in-order (left → node → right). Maintain a counter that increments with each node visited. When the counter equals k, return the current node’s value.

⏱ Time O(n) Worst case: visit all nodes 💾 Space O(h)

Step-by-step Example

Input: Tree with values [3, 1, 4, 2], k = 1

In-order sequence: [1, 2, 3, 4]

Step	Node	count	Action
1	1	1	count == k, return 1 ✓

Animated walkthrough

How in-order DFS finds the kth smallest element

Watch the count increment as nodes are visited in sorted order. Stop when count reaches k.

Back Autoplay Next Reset

Step 1 of 2 Target: 1

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function kthSmallest_inorder(root, k):
    count = 0
    result = null

    function inorder(node):
        if node is null or result is not null:
            return

        inorder(node.left)

        count++
        if count == k:
            result = node.val
            return

        inorder(node.right)

    inorder(root)
    return result

Solution Code

Python

kth_smallest_element_in_bst_inorder.py

from typing import Optional


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


def kth_smallest_inorder_dfs(root: Optional[TreeNode], k: int) -> int:
    """
    In-order DFS approach to find kth smallest element in BST.

    In-order traversal of BST yields sorted sequence.
    Count nodes as we traverse, return when we reach the kth node.

    Time: O(k) in best case, O(n) in worst case
    Space: O(h) - recursion stack, h = height
    """
    count = [0]
    result = [None]

    def inorder(node):
        if not node or result[0] is not None:
            return

        # Traverse left subtree
        inorder(node.left)

        # Process current node
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return

        # Traverse right subtree
        inorder(node.right)

    inorder(root)
    return result[0]


# Test cases
if __name__ == "__main__":
    # Example 1: Find 1st smallest
    root1 = TreeNode(3)
    root1.left = TreeNode(1)
    root1.right = TreeNode(4)
    root1.left.right = TreeNode(2)
    print(kth_smallest_inorder_dfs(root1, 1))  # 1

    # Example 2: Find 3rd smallest
    print(kth_smallest_inorder_dfs(root1, 3))  # 2

C++

kth_smallest_element_in_bst_inorder.cpp

#include <iostream>
using namespace std;

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

class Solution {
private:
    int count = 0;
    int result = -1;

    void inorder(TreeNode* node, int k) {
        if (!node || result != -1) return;

        // Traverse left subtree
        inorder(node->left, k);

        // Process current node
        count++;
        if (count == k) {
            result = node->val;
            return;
        }

        // Traverse right subtree
        inorder(node->right, k);
    }

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

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;  // 1
    cout << sol.kthSmallest(root, 3) << endl;  // 2

    return 0;
}

Java

KthSmallestElementInBST_inorder.java

public class KthSmallestInBST_InorderDFS {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    private int count = 0;
    private int result = -1;

    private void inorder(TreeNode node, int k) {
        if (node == null || result != -1) return;

        // Traverse left subtree
        inorder(node.left, k);

        // Process current node
        count++;
        if (count == k) {
            result = node.val;
            return;
        }

        // Traverse right subtree
        inorder(node.right, k);
    }

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

    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);

        KthSmallestInBST_InorderDFS sol = new KthSmallestInBST_InorderDFS();
        System.out.println(sol.kthSmallest(root, 1));  // 1
        System.out.println(sol.kthSmallest(root, 3));  // 2
    }
}

JavaScript

kth_smallest_element_in_bst_inorder.js

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

function kthSmallestInorderDFS(root, k) {
    let count = 0;
    let result = null;

    function inorder(node) {
        if (!node || result !== null) return;

        // Traverse left subtree
        inorder(node.left);

        // Process current node
        count++;
        if (count === k) {
            result = node.val;
            return;
        }

        // Traverse right subtree
        inorder(node.right);
    }

    inorder(root);
    return result;
}

// Test cases
const root = new TreeNode(3);
root.left = new TreeNode(1);
root.right = new TreeNode(4);
root.left.right = new TreeNode(2);

console.log(kthSmallestInorderDFS(root, 1));  // 1
console.log(kthSmallestInorderDFS(root, 3));  // 2

Rust

kth_smallest_element_in_bst_inorder.rs

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

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

pub fn kth_smallest_inorder_dfs(
    root: Option<Rc<RefCell<TreeNode>>>,
    k: i32,
) -> i32 {
    let mut count = 0;
    let mut result: Option<i32> = None;

    fn inorder(
        node: &Option<Rc<RefCell<TreeNode>>>,
        count: &mut i32,
        result: &mut Option<i32>,
        k: i32,
    ) {
        if result.is_some() {
            return;
        }

        if let Some(n) = node {
            let n = n.borrow();

            // Traverse left subtree
            inorder(&n.left, count, result, k);

            // Process current node
            *count += 1;
            if *count == k {
                *result = Some(n.val);
                return;
            }

            // Traverse right subtree
            inorder(&n.right, count, result, k);
        }
    }

    inorder(&root, &mut count, &mut result, k);
    result.unwrap_or(-1)
}

fn main() {
    let root = Rc::new(RefCell::new(TreeNode::new(3)));
    let left = Rc::new(RefCell::new(TreeNode::new(1)));
    let right = Rc::new(RefCell::new(TreeNode::new(4)));
    let left_right = Rc::new(RefCell::new(TreeNode::new(2)));

    root.borrow_mut().left = Some(left.clone());
    root.borrow_mut().right = Some(right);
    left.borrow_mut().right = Some(left_right);

    println!("{}", kth_smallest_inorder_dfs(Some(root.clone()), 1));  // 1
    println!("{}", kth_smallest_inorder_dfs(Some(root), 3));  // 2
}

Go

kth_smallest_element_in_bst_inorder.go

package main

import "fmt"

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

func KthSmallestInorderDFS(root *TreeNode, k int) int {
    var count int
    var result int = -1

    var inorder func(*TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil || result != -1 {
            return
        }

        // Traverse left subtree
        inorder(node.Left)

        // Process current node
        count++
        if count == k {
            result = node.Val
            return
        }

        // Traverse right subtree
        inorder(node.Right)
    }

    inorder(root)
    return result
}

func main() {
    root := &TreeNode{Val: 3}
    root.Left = &TreeNode{Val: 1}
    root.Right = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 2}

    fmt.Println(KthSmallestInorderDFS(root, 1))  // 1
    fmt.Println(KthSmallestInorderDFS(root, 3))  // 2
}

Approach 2: Morris In-Order Traversal

advanced

Morris traversal enables in-order traversal without recursion or an explicit stack. It uses “threading” — temporary pointers to connect nodes. This achieves O(1) space.

The algorithm works in two passes per node: on the first visit, create a thread back to the current node; on the second visit, remove the thread and process the node.

⏱ Time O(n) All nodes visited 💾 Space O(1) No extra structure

Step-by-step Example

Input: Tree with values [3, 1, 4, 2], k = 1

1. Start at 3 (root).
2. Find predecessor of 3: it’s 2.
3. Thread 2 → 3 (first visit to 2).
4. Move to left child 1.
5. 1 has no left child. Visit 1, count = 1. Return 1.

Pseudocode

function kthSmallest_morris(root, k):
    count = 0
    current = root

    while current is not null:
        if current.left is null:
            // No left child: visit current node
            count++
            if count == k:
                return current.val
            current = current.right
        else:
            // Find in-order predecessor
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right

            if predecessor.right is null:
                // First visit: create thread
                predecessor.right = current
                current = current.left
            else:
                // Second visit: remove thread, process current
                predecessor.right = null
                count++
                if count == k:
                    return current.val
                current = current.right

    return -1

Solution Code

Python

kth_smallest_element_in_bst_morris.py

from typing import Optional


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


def kth_smallest_morris_inorder(root: Optional[TreeNode], k: int) -> int:
    """
    Morris In-Order traversal to find kth smallest element in BST.

    Uses tree threading to traverse without recursion or extra stack space.
    Space-efficient: O(1) extra space (modifying and restoring tree structure).

    Time: O(n) - visit each node twice
    Space: O(1) - no extra data structures
    """
    count = 0
    current = root

    while current:
        if current.left is None:
            # Left is None, process current node
            count += 1
            if count == k:
                return current.val
            current = current.right
        else:
            # Find in-order predecessor
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right

            if predecessor.right is None:
                # Create link to current node
                predecessor.right = current
                current = current.left
            else:
                # Link exists, remove it and process current
                predecessor.right = None
                count += 1
                if count == k:
                    return current.val
                current = current.right

    return -1


# Test cases
if __name__ == "__main__":
    # Example 1: Find 1st smallest
    root1 = TreeNode(3)
    root1.left = TreeNode(1)
    root1.right = TreeNode(4)
    root1.left.right = TreeNode(2)
    print(kth_smallest_morris_inorder(root1, 1))  # 1

    # Example 2: Find 3rd smallest
    print(kth_smallest_morris_inorder(root1, 3))  # 2

C++

kth_smallest_element_in_bst_morris.cpp

#include <iostream>
using namespace std;

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

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int count = 0;
        TreeNode* current = root;

        while (current) {
            if (!current->left) {
                // Left is null, process current node
                count++;
                if (count == k) {
                    return current->val;
                }
                current = current->right;
            } else {
                // Find in-order predecessor
                TreeNode* predecessor = current->left;
                while (predecessor->right && predecessor->right != current) {
                    predecessor = predecessor->right;
                }

                if (!predecessor->right) {
                    // Create link to current node
                    predecessor->right = current;
                    current = current->left;
                } else {
                    // Link exists, remove it and process current
                    predecessor->right = nullptr;
                    count++;
                    if (count == k) {
                        return current->val;
                    }
                    current = current->right;
                }
            }
        }

        return -1;
    }
};

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;  // 1
    cout << sol.kthSmallest(root, 3) << endl;  // 2

    return 0;
}

Java

KthSmallestElementInBST_morris.java

public class KthSmallestInBST_MorrisInorder {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public int kthSmallest(TreeNode root, int k) {
        int count = 0;
        TreeNode current = root;

        while (current != null) {
            if (current.left == null) {
                // Left is null, process current node
                count++;
                if (count == k) {
                    return current.val;
                }
                current = current.right;
            } else {
                // Find in-order predecessor
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }

                if (predecessor.right == null) {
                    // Create link to current node
                    predecessor.right = current;
                    current = current.left;
                } else {
                    // Link exists, remove it and process current
                    predecessor.right = null;
                    count++;
                    if (count == k) {
                        return current.val;
                    }
                    current = current.right;
                }
            }
        }

        return -1;
    }

    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);

        KthSmallestInBST_MorrisInorder sol = new KthSmallestInBST_MorrisInorder();
        System.out.println(sol.kthSmallest(root, 1));  // 1
        System.out.println(sol.kthSmallest(root, 3));  // 2
    }
}

JavaScript

kth_smallest_element_in_bst_morris.js

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

function kthSmallestMorrisInorder(root, k) {
    let count = 0;
    let current = root;

    while (current) {
        if (!current.left) {
            // Left is null, process current node
            count++;
            if (count === k) {
                return current.val;
            }
            current = current.right;
        } else {
            // Find in-order predecessor
            let predecessor = current.left;
            while (predecessor.right && predecessor.right !== current) {
                predecessor = predecessor.right;
            }

            if (!predecessor.right) {
                // Create link to current node
                predecessor.right = current;
                current = current.left;
            } else {
                // Link exists, remove it and process current
                predecessor.right = null;
                count++;
                if (count === k) {
                    return current.val;
                }
                current = current.right;
            }
        }
    }

    return -1;
}

// Test cases
const root = new TreeNode(3);
root.left = new TreeNode(1);
root.right = new TreeNode(4);
root.left.right = new TreeNode(2);

console.log(kthSmallestMorrisInorder(root, 1));  // 1
console.log(kthSmallestMorrisInorder(root, 3));  // 2

Rust

kth_smallest_element_in_bst_morris.rs

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

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

pub fn kth_smallest_morris_inorder(
    root: Option<Rc<RefCell<TreeNode>>>,
    k: i32,
) -> i32 {
    if root.is_none() {
        return -1;
    }

    let mut count = 0;
    let mut current = root;

    while let Some(node) = current {
        let mut node_ref = node.borrow_mut();

        if node_ref.left.is_none() {
            // Left is null, process current node
            count += 1;
            if count == k {
                return node_ref.val;
            }
            current = node_ref.right.take();
        } else {
            // Find in-order predecessor
            let left = node_ref.left.take();
            let mut pred = left.clone();

            loop {
                let pred_ref = pred.borrow();
                if pred_ref.right.is_none() || pred_ref.right.as_ref() == Some(&node) {
                    break;
                }
                let next = pred_ref.right.clone();
                drop(pred_ref);
                pred = next.unwrap();
            }

            let mut pred_ref = pred.borrow_mut();
            if pred_ref.right.is_none() {
                // Create link to current node
                pred_ref.right = Some(node.clone());
                node_ref.left = left;
                current = Some(node.clone());
            } else {
                // Link exists, remove it and process current
                pred_ref.right = None;
                drop(pred_ref);
                drop(node_ref);

                count += 1;
                if count == k {
                    return node.borrow().val;
                }

                let right = node.borrow_mut().right.take();
                current = right;
            }
        }
    }

    -1
}

fn main() {
    let root = Rc::new(RefCell::new(TreeNode::new(3)));
    let left = Rc::new(RefCell::new(TreeNode::new(1)));
    let right = Rc::new(RefCell::new(TreeNode::new(4)));
    let left_right = Rc::new(RefCell::new(TreeNode::new(2)));

    root.borrow_mut().left = Some(left.clone());
    root.borrow_mut().right = Some(right);
    left.borrow_mut().right = Some(left_right);

    println!("{}", kth_smallest_morris_inorder(Some(root.clone()), 1));  // 1
    println!("{}", kth_smallest_morris_inorder(Some(root), 3));  // 2
}

Go

kth_smallest_element_in_bst_morris.go

package main

import "fmt"

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

func KthSmallestMorrisInorder(root *TreeNode, k int) int {
    var count int
    current := root

    for current != nil {
        if current.Left == nil {
            // Left is null, process current node
            count++
            if count == k {
                return current.Val
            }
            current = current.Right
        } else {
            // Find in-order predecessor
            predecessor := current.Left
            for predecessor.Right != nil && predecessor.Right != current {
                predecessor = predecessor.Right
            }

            if predecessor.Right == nil {
                // Create link to current node
                predecessor.Right = current
                current = current.Left
            } else {
                // Link exists, remove it and process current
                predecessor.Right = nil
                count++
                if count == k {
                    return current.Val
                }
                current = current.Right
            }
        }
    }

    return -1
}

func main() {
    root := &TreeNode{Val: 3}
    root.Left = &TreeNode{Val: 1}
    root.Right = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 2}

    fmt.Println(KthSmallestMorrisInorder(root, 1))  // 1
    fmt.Println(KthSmallestMorrisInorder(root, 3))  // 2
}

Common mistakes

Watch for these pitfalls

• Counting from 0 vs 1: The problem uses 1-indexed k. Ensure your counter starts at 0 and increments before checking k.
• Early termination: Once the kth element is found, avoid further recursion. Use a flag or check result != null.
• Off-by-one errors in Morris: Ensure threads are created and removed correctly during first and second visits.
• Modifying the tree (Morris): Morris traversal temporarily modifies the tree. Ensure threads are restored for re-entrant code.

Related Problems

• Minimum Absolute Difference in BST ↗ Easy #530
• Validate Binary Search Tree ↗ Medium #98
• Lowest Common Ancestor of a BST ↗ Easy #235
• Binary Tree Inorder Traversal ↗ Easy #94

Interview Tips

Key trade-offs to discuss

• DFS vs Morris: DFS is simpler and more intuitive. Morris is an advanced technique that shows deep understanding of tree traversal.
• Space complexity: In-Order DFS uses O(h) recursion stack. For balanced trees, h = log(n). For skewed trees, h = n.
• Follow-up: “Can you solve this in O(log n) time if the BST is augmented with subtree sizes?” Yes — use binary search within the tree structure.
• Edge cases: k = 1 (smallest element), k = n (largest element), single-node trees.

← Previous
#229 Majority Element II Next
#231 Power of Two →