deepSWE.io

Kth Smallest Element in a BST

TreeDFSBST

15 min

Problem Statement

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.

Example

Example 1:

Input: root = [5,3,7,2,4,6,8,1], k = 4

Output: 4

Constraints

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

Approach 1: Recursive In-order Traversal

The solution uses a recursive in-order traversal (left, root, right) to visit the nodes of the BST in ascending order. We can stop the traversal once we've found the kth smallest element.

Algorithm Steps

Perform a recursive in-order traversal of the BST.
Keep a counter to track the number of nodes visited.
When the counter reaches k, the current node's value is the kth smallest element.

Start: Find the 4th smallest element (k=4).

Kth Smallest Element in a BST Solution


# Definition for a binary tree node.
# 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: Optional[TreeNode], k: int) -> int:
        self.k = k
        self.res = 0
        self.inorder(root)
        return self.res
    
    def inorder(self, node):
        if not node:
            return
        
        self.inorder(node.left)
        self.k -= 1
        if self.k == 0:
            self.res = node.val
            return
        self.inorder(node.right)

Approach 2: Iterative In-order Traversal

The solution uses an iterative in-order traversal with a stack to visit the nodes of the BST in ascending order. This avoids recursion and can be more efficient in terms of memory for very deep trees.

Algorithm Steps

Use a stack to store nodes.
Push all left children of the current node onto the stack.
Pop a node, decrement k, and if k is 0, this is the kth smallest element.
Move to the right child of the popped node and repeat.

Start: Find the 4th smallest element (k=4).

Kth Smallest Element in a BST Solution


# Definition for a binary tree node.
# 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: Optional[TreeNode], k: int) -> int:
        stack = []
        
        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right