Kth Smallest Integer in BST

Problem Statement

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

A binary search tree satisfies the following constraints:

  • The left subtree of every node contains only nodes with keys less than the node’s key.
  • The right subtree of every node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees are also binary search trees.

Example 1:

Input: root = [2,1,3], k = 1
Output: 1

Example 2:

Input: root = [4,3,5,2,null], k = 4
Output: 5

Constraints:

  • 1 <= k <= The number of nodes in the tree <= 1000.
  • 0 <= Node.val <= 1000

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the number of nodes in the given tree.

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the number of nodes in the given tree.

Hint 1

A naive solution would be to store the node values in an array, sort it, and then return the k-th value from the sorted array. This would be an O(n log n) solution due to sorting. Can you think of a better way? Maybe you should try one of the traversal techniques.

Hint 2

We can use the Depth First Search (DFS) algorithm to traverse the tree. Since the tree is a Binary Search Tree (BST), we can leverage its structure and perform an in-order traversal, where we first visit the left subtree, then the current node, and finally the right subtree. Why? Because we need the k-th smallest integer, and by visiting the left subtree first, we ensure that we encounter smaller nodes before the current node. How can you implement this?

Hint 3

We keep a counter variable cnt to track the position of the current node in the ascending order of values. When cnt == k, we store the current node’s value in a global variable and return. This allows us to identify and return the k-th smallest element during the in-order traversal.

Solution

Brute Force

# 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
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(root: Optional[TreeNode], k: int) -> int:
arr = []
def dfs(node):
if not node:
return
arr.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
arr.sort()
return arr[k - 1]

Time complexity: O(n log n) Space complexity: O(n)

Inorder Traversal

# 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
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(root: Optional[TreeNode], k: int) -> int:
arr = []
def dfs(node):
if not node:
return
dfs(node.left)
arr.append(node.val)
dfs(node.right)
dfs(root)
return arr[k - 1]

Time complexity: O(n) Space complexity: O(n)

Recursive DFS (Optimal)

# 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
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(root: Optional[TreeNode], k: int) -> int:
cnt = k
res = root.val
def dfs(node):
nonlocal cnt, res
if not node:
return
dfs(node.left)
cnt -= 1
if cnt == 0:
res = node.val
return
dfs(node.right)
dfs(root)
return res

Time complexity: O(n) Space complexity: O(n)

Iterative DFS (Optimal)

# 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
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(root: Optional[TreeNode], k: int) -> int:
stack = []
curr = root
while stack or curr:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
k -= 1
if k == 0:
return curr.val
curr = curr.right

Time complexity: O(n) Space complexity: O(n)

Morris Traversal

# 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
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(root: Optional[TreeNode], k: int) -> int:
curr = root
while curr:
if not curr.left:
k -= 1
if k == 0:
return curr.val
curr = curr.right
else:
pred = curr.left
while pred.right and pred.right != curr:
pred = pred.right
if not pred.right:
pred.right = curr
curr = curr.left
else:
pred.right = None
k -= 1
if k == 0:
return curr.val
curr = curr.right
return -1

Time complexity: O(n) Space complexity: O(1)