[Top Interview 150] 230. Kth Smallest Element in a BST

Solution)

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        # A list that will save values of nodes in an increasing order
        res = []

        # Helper function that will save values to res
        def dfs(root):
            # Base Case
            if not root: return
            
            # Append vals in inorder traversal, which gives us
            # the increasing order
            dfs(root.left)

            # Mark res as nonlocal for us to use it
            # in an inner function
            nonlocal res
            res.append(root.val)
    
            dfs(root.right)
            
        dfs(root)
        return res[k-1]

 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(n)
*n = number of nodes in a tree
 

Explanation)

We'll iterate BST using inorder traversal. By traversing in inorder, we'll always get nodes in increasing order due to BST's property.
 
While traversing the tree, append the values in increasing order to a list and return (k-1)th elemnt of that list.
 

1. Initialization)

Our approach is to get a list of nodes' values in an increasing order. Once we have a full list of values in an increasing order, we'll return k-1th element in that list.
 

def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        # 1. Initialization
        res = []

 

2. Helper Function)

We'll use a recursive helper function to append values to res in an increasing order.
 
As always, our base case of an empty tree will return None.
 
Then to get values from smallest to biggest, we'll iterate the tree in inorder traversal.
 
Because BST root saves smaller nodes to its left and bigger nodes to its right, appending nodes' values in inorder traversal will give us a list in an increasing order.
 
The keyword nonlocal allows us to use the variable res. Because res is defined inbetween two functions, we need to use the keyword to access res in an inner function.
 

def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        # 1. Initialization
        res = []

        # 2. Helper function
        def dfs(root):
            if not root: return
            
            dfs(root.left)

            nonlocal res
            res.append(root.val)
    
            dfs(root.right)

 

3. Run the helper function)

Once we define the helper function, run it which will give us res filled with values in an increasing order.
 
Last step is to return kth smallest element. However, we need to return k-1th element in res. This is because Python's lists are 0-indexed.  
 
So res's k-1th element is the kth smallest value in the tree.
 

def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        # 1. Initialization
        res = []

        # 2. Helper function
        def dfs(root):
            if not root: return
            
            dfs(root.left)

            nonlocal res
            res.append(root.val)
    
            dfs(root.right)
        
        # 3. Run the helper function
        dfs(root)
        return res[k-1]

 
 
 
I wanted to solve the problem without using extra space, but this was the cleanest solution I could get. I looked at other solutions in leecode, but sadly all of the solutions were similar to my solution.
 
Enjoy your life!