Leetcode: Kth Smallest Element in a BST (Kotlin)
Kotlin

Leetcode: Kth Smallest Element in a BST (Kotlin)

2024-03-20
10 min read

Leetcode — Kth Smallest Element in a BST (Kotlin)

Kth Smallest Element in a BST - LeetCode

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.

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

Example 1:

Example 2:

Constraints:

Since this is a Binary Search Tree we can do an inorder traversal to get the values sorted.

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.

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

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

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

  4. Return list[k-1] as our answer. They mention “k” starts at 1 indexed. {% gist https://gist.github.com/cmcoffeedev/6db4eba4e3d96424d33f9133bb2d8aff.js %}

Iterative Inorder Traversal

  1. Create a stack of nullable TreeNode

  2. 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.

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

  4. The inner while loop will traverse all of temps left children and push them to the stack.

  5. 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.

  6. 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

  7. Repeat the process

Alternatively we can add the values to a list and return list[k-1] as we did in the recursive traversal. {% gist https://gist.github.com/cmcoffeedev/1671cea5a0bc2a912b4d09490f88288d.js %}