Leetcode-Kth Smallest Element in a BST(Kotlin)
Post
Cancel

# Leetcode-Kth Smallest Element in a BST(Kotlin)

## Overview

### What You’ll Learn

This is a medium Leetcode problem that wants you to find the kth smallest value (1-indexed) of every value in the Binary Search Tree. I will show you two approaches I took to solve this. Since this is a Binary Search Tree we can do an inorder traversal to get the values sorted.

First I will show you the problem statement, examples and constraints given.

Also, check out this video tutorial on implementing these solutions:

## Recursive Inorder Traversal

For the recursive inorder solution we can create an ArrayList of Int and pass it to our inorderTraversal function. We can add the values to the list at each recursive call.

• Create an ArrayList of Int and pass it to our inorderTraversal function.

• For the inorderTraversal function, we will have a base case that returns if the tree node passed is null

• Add the values to the list at each recursive call.

• Return list[k-1] as our answer. They mention “k” starts at 1 indexed.

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { fun kthSmallest(root: TreeNode?, k: Int): Int { val list = ArrayList<Int>() inorderTraversal(list, root) return list[k-1] } fun inorderTraversal(list: ArrayList<Int>, root: TreeNode?){ if(root == null) return inorderTraversal(list, root.left) list.add(root.`val`) inorderTraversal(list, root.right) } } ```

## Iterative Inorder Traversal

• Create a stack of nullable TreeNode
• root and k are immutable so we need to create mutable copies. We can create a variable called temp or current as a copy for the root TreeNode. We can use indexToFind as a copy for k.

• We will have nested while loops. The outer most while-loop will check if temp is null or the stack is empty.

• The inner while loop will traverse all of temps left children and push them to the stack.
• After traversing the left children we will eventually hit a null node. We can then pop from the stack and set that node as temp, which will be the last leaf node we touched.

• We can pre decrement the indexToFind variable each time we get to this point. When the value is 0, we have found the index we are looking for so we can return the value. Set temp to temp’s right child

• Repeat the process

Alternatively we can add the values to a list and return list[k-1] as we did in the recursive traversal.

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { fun kthSmallest(root: TreeNode?, k: Int): Int { val stack = Stack<TreeNode?>() var temp = root var indexToFind = k while(temp != null || stack.size > 0){ while(temp != null){ stack.push(temp) temp = temp.left } temp = stack.pop() temp?.let{ node -> if(--indexToFind == 0) return node.`val` temp = node.right } } return -1 } } ```

## Congratulations

Congratulations, we have went through a couple of ways to solve Leetcode - Kth Smallest Element in a BST (Kotlin)!

Also, check out the video tutorial on implementing these solutions: