Explanation for Leetcode 230: Kth Smallest Element in BST - Solution Code in Java and JavaScript

This intermediate Leetcode problem may seem challenging but it's not once you understand the traversal and the basics of binary search trees.

To solve this problem you would have to do an in-order traversal. If you're not familiar with traversing a binary search tree, you can learn more by reading this article here:

Preorder, Inorder, Postorder Traversal with Binary Trees

Let's review what we already know about binary search trees and inorder traversal. A binary search tree is similar to a binary tree except the left node has a value that is less than its parent node and the right child has a value that is greater than its parent node:

value of left child < value of node < value of right child

When you do an in-order traversal of a binary search tree, you're going to visit the left subtree first and will access the smallest values first. So now that a review of a binary search tree and an inorder traversal is done, let's look at the approach needed to solve this problem.

Solution

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

We need to check that the root has a left and right child, and if not, return the root value. We then declare and initialize an array(or ArrayList with type Integer if using Java). Next, implement our special inorder traversal. We have two base cases for our inorder traversal function: One for checking that the root is null and the other one to see that the length of our array is equal to k. So each time we traverse through the list from node to node, we traverse to the left, add the current root's value, and then traverse to the right. This will repeat until one of the two base cases is true.

class Solution {
    //O(n)
    public int kthSmallest(TreeNode root, int k) {
        if(root.left == null && root.right == null) {
            return root.val;
        }

        List<Integer> mins = new ArrayList<>();

        inorder(root, mins, k);

        return mins.get(k - 1);
    }

    //O(n)
    public void inorder(TreeNode root, List<Integer> mins, int k) {
        if(root == null) return;
        if(mins.size() == k) return;

        inorder(root.left, mins, k);

        mins.add(root.val);

        inorder(root.right, mins, k);
    }
}

var kthSmallest = function(root, k) {
    if(root.left == null && root.right == null) {
        return root.val;
    } 

    let mins = [];

    inorder(root, mins, k);

    return mins[k-1];
};

function inorder(root, mins, k) {
    if(root == null) return;
    if(mins.length == k) return;
    inorder(root.left, mins, k);

    mins.push(root.val);

    inorder(root.right, mins);
}

In conclusion, this problem is easy once you understand the difference between a binary tree and a binary search tree as well as understanding how in-order traversal works.