Kth Smallest Element in a BST
Kth Smallest Element in a BST
Welcome to the enchanted forest of Binary Search Trees (BST)! Imagine you are a magical creature tasked with finding the magical 'kth' smallest treasure in the forest. A BST is structured in such a way that for every node, the nodes in the left subtree are smaller, and the nodes in the right subtree are greater.
Your task is to write a function kth_smallest that finds the kth smallest element in a binary search tree (BST).
Example of a BST:
Let's say our BST looks like this:
5
/ \
3 7
/ \ / \
2 4 6 8
If we were to list the elements in ascending order, they would be 2, 3, 4, 5, 6, 7, 8. So:
- The 1st smallest element is 2
- The 2nd smallest element is 3
- The 3rd smallest element is 4, and so on.
Your Mission:
Write a function kth_smallest that takes a BST represented by its root node and an integer k, and returns the kth smallest element in the BST.
Function Signature
def kth_smallest(root: TreeNode, k: int) -> int:
Example:
# Let's represent our BST with TreeNode objects
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
root = TreeNode(5)
root.left = TreeNode(3, TreeNode(2), TreeNode(4))
root.right = TreeNode(7, TreeNode(6), TreeNode(8))
print(kth_smallest(root, 3)) # Output should be 4
Have fun on your exploration through the BSTs! Remember, patience and a systematic approach will help you find the treasures. Good luck!
How the tests work
Each test gives the tree as nested val, left and right entries, plus k. The tree is built for you from TreeNode objects.
Inputs
Arg 1:
{"val":5,"left":{"val":3,"left":{"val":2,"left":null,"right":null},"right":{"val":4,"left":null,"right":null}},"right":{"val":7,"left":{"val":6,"left":null,"right":null},"right":{"val":8,"left":null,"right":null}}}Arg 2:
3Expected Output
4Actual Output