Kth Smallest Element in a BST

Advanced

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.

Geek
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:

3
Expected Output
4
Actual Output
Kth Smallest Element in a BST [advanced] | Coding for Kids