Kth Smallest Element in a BST

To find the kth smallest element in a binary search tree (BST), we can perform an in-order traversal of the tree. In an in-order traversal, the elements will be visited in ascending order, so the kth element visited will be the kth smallest element.

Here’s the code:

1
2
3
4
5
6
7
8
9
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        def inOrderTraversal(node):
            if not node:
                return []
            return inOrderTraversal(node.left) + [node.val] + inOrderTraversal(node.right)

        sorted_values = inOrderTraversal(root)
        return sorted_values[k - 1]

This code defines an inOrderTraversal function that returns a list of values from the tree in ascending order. We then return the kth value from this sorted list (using 0-based indexing).

This approach has a time complexity of O(n) and a space complexity of O(n), where n is the number of nodes in the tree.

Claude

Here is an Python implementation to find the kth smallest element in a binary search tree:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        n = 0
        stack = []
        curr = root

        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left

            curr = stack.pop()
            n += 1
            if n == k:
                return curr.val

            curr = curr.right
        

The key ideas are:

Traverse the tree in-order using a stack. This visits nodes in ascending order.
Keep track of how many nodes have been visited.
Once k nodes have been visited, return the current node’s value.
In-order traversal allows us to traverse the BST in sorted order without having to generate the entire sorted array.

Time complexity is O(H + k) where H is the tree height, since in the worst case we traverse the height of the tree plus k nodes.

Space complexity is O(H) for the stack, also bounded by the tree height.

So this leverages in-order traversal to efficiently find the kth smallest element in a BST without needing to sort the entire tree.

My Notes

Define the Interface Input: TreeNode instance (root) and integer k Output: Integer (the kth smallest element)
Should I check every node in the BST? Is there a way to reduce the search space.
Traversal: Traverse the tree inorder Example 1: 1,2,3,4 Return 1 Example 2: 1,2,3,4,5,6 Return 3
How do I avoid unnecessary work?
Recursive Approach Base Case
- When we hit the leaf node
We will make two recursive calls One for left subtree One for right subtree
Unit of Work Add the node value to a list
The kth smallest element method will take the list and index into the k-1 element and return

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def inorder(node, k)
  if node.nil?
      return
  end

  inorder(node.left, k)
    @counter -= 1 
    if @counter == 0
        @result = node.val
        return 
    end

   inorder(node.right, k)
end
def kth_smallest(root, k)
    @counter = k
    inorder(root, k)
    @result
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def kthSmallest(root, k):
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        k -= 1
        if k == 0:
            return root.val
        root = root.right

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @param {Integer} k
# @return {Integer}
def kth_smallest(root, k)
  stack = []

    while root or stack
       while root
          stack.append(root)
           root = root.left
       end
       root = stack.pop
        k -= 1
        if k == 0
            return root.val
        end
        root = root.right
    end
end