Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
March 25, 2022 02:01 am GMT

Leetcode Kth Smallest Element in a BST (Kotlin)

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.

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

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

Image description

Image description

Image description

Image description

Since this is a Binary Search Tree we can do an in-order 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.

Iterative Inorder Traversal

  1. Create a stack of nullable TreeNode
    root and k are immutable so we need to create mutable copies.

  2. 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 temps right child.

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

Codelab version of this solution: https://cmcoffeedev.com/codelabs/leetcode-kth-smallest/index.html?index=..%2F..index#0

Video Solution:


Original Link: https://dev.to/cmcoffeedev/leetcode-kth-smallest-element-in-a-bst-kotlin-4m9

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To