Kth Smallest Element in a BST

Given a binary search tree, write a function kth Smallest to find the kth smallest element in it. Tags: Tree

Try It!

Discussion

Video

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: TreeNode, k: int) -> int:
        lst = []
        self.helper(root, lst)
        return lst[k - 1]
    
    def helper(self, root, lst):
        # perform an inorder traversal
        if not root:
            return
        
        self.helper(root.left, lst)
        lst.append(root.val)
        self.helper(root.right, lst)