I hope you already know about Binary Search Tree. In BST, each node is greater than its left subtree and smaller than its right subtree.
If we print all the nodes of a BST using an inorder traversal algorithm, we will get the sorted value in ascending order. Inorder traversal follows the rule: left – root/value – right. To solve this problem, we can store these values in an array.
Let’s think about the following BST.
10
/ \
7 12
/ \ \
5 9 15If we traverse the above tree using an inorder traversal algorithm and store it in an array, we will get this: [5, 7, 9, 10, 12, 15]. It’s sorted in ascending order.
If we want to access the kth smallest value from the array, we can use k as the index number. As the index starts from 0, we subtract one from the k. And then we will get the result.
If k = 2, then the output will be array[k-1] => 7. That means 7 is the 2nd smallest element in the BST.
Let’s see the code.
# 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:
res = []
def dfs(root):
if root:
dfs(root.left)
res.append(root.val)
dfs(root.right)
dfs(root)
return res[k-1]We use recursion for the previous solution. We can solve this problem another way using an iterative solution.
We don’t use any extra array in this solution. But the time complexity won’t change. For both solutions, time and space complexity will be O(n).
In this iterative solution, we will track the number of visited nodes. As we will use the inorder traversal algorithm in BST, it will start traversing smallest to largest. When the number of visited nodes raches k times, we will return that node.
Let’s see the iterative 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 = []
count = 0
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
count += 1
if k == count:
return root.val
root = root.rightI hope you got the idea about the solution. Thanks for reading.
Happy Learning.
Happy Coding.