Kth Smallest Element in BST
Statement
Given the root node of a binary search tree and an integer k, find the kth smallest value in the tree.
Constraints
- number of nodes =
n - 1 ≤
k≤n≤ 500 - 0 ≤
node.data≤ 10⁴
Solution
"""
production algorithm
"""
class Solution:
def kth_smallest_element(self, root, k):
"""
time complexity O(n)
space complexity O(n)
"""
count, result = [k], []
self.kth_smallest_element_helper(root, count, result)
return result[0]
def kth_smallest_element_helper(self, root, count, result):
"""
time complexity O(n)
space complexity O(n)
"""
if result:
return
if root is None:
return
self.kth_smallest_element_helper(root.left, count, result)
count[0] -= 1
if count[0] == 0:
result.append(root.data)
self.kth_smallest_element_helper(root.right, count, result)"""
unit tests
"""
from unittest import TestCase
from algorithms.dfs.kth_smallest_element_in_bst.solution import Solution
from data_structures.binary_tree.binary_tree import BinaryTreeNode
class SolutionTestCase(TestCase):
def test_0th_smallest_element(self):
# Given
root = BinaryTreeNode(9)
root.left = BinaryTreeNode(3)
root.right = BinaryTreeNode(11)
root.left.left = BinaryTreeNode(-1)
root.left.right = BinaryTreeNode(6)
root.right.left = BinaryTreeNode(10)
root.right.right = BinaryTreeNode(16)
root.right.right.right = BinaryTreeNode(18)
k = 1
solution = Solution()
# When
actual = solution.kth_smallest_element(root, k)
# Then
expected = -1
self.assertEqual(actual, expected)
def test_kth_smallest_element(self):
# Given
root = BinaryTreeNode(9)
root.left = BinaryTreeNode(3)
root.right = BinaryTreeNode(11)
root.left.left = BinaryTreeNode(-1)
root.left.right = BinaryTreeNode(6)
root.right.left = BinaryTreeNode(10)
root.right.right = BinaryTreeNode(16)
root.right.right.right = BinaryTreeNode(18)
k = 5
solution = Solution()
# When
actual = solution.kth_smallest_element(root, k)
# Then
expected = 10
self.assertEqual(actual, expected)
def test_nth_smallest_element(self):
# Given
root = BinaryTreeNode(9)
root.left = BinaryTreeNode(3)
root.right = BinaryTreeNode(11)
root.left.left = BinaryTreeNode(-1)
root.left.right = BinaryTreeNode(6)
root.right.left = BinaryTreeNode(10)
root.right.right = BinaryTreeNode(16)
root.right.right.right = BinaryTreeNode(18)
k = 8
solution = Solution()
# When
actual = solution.kth_smallest_element(root, k)
# Then
expected = 18
self.assertEqual(actual, expected)Strategy
Depth First Search.
Explanation
The algorithm does an inorder traversal of the binary search tree. It counts the number of nodes seen so far, so that when it finds the kth element, it saves that element. When the kth smallest element has been found, the algorithm backs out of recursion, and then returns the result.
Time Complexity
At most, the algorithm walks every node of the binary search tree. Let n be the number of nodes in the binary search tree. Then, the time complexity of the algorithm is O(n).
Space Complexity
At most, the algorithm walks every node in the binary search tree, and the binary search tree is a degenerate tree. The depth of recursion would reach n, where n is the number of nodes in the binary search tree. Therefore, the auxiliary space complexity of the algorithm is O(n).
