Kth Smallest Element in a BST, solving Netflix Interview question.

Question: Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Eg : Input: root = [5,3,6,2,4,null,null,1], k = 3

       5
      / \
     3   6
    / \
   2   4
  /
 1

Output: 3

Let's solve this.

First, we need to traverse the tree, but how?

Looking at the question we can see that it's a BST it a Binary Search Tree.

A binary search tree has the following properties :
1 > All the elements on the left subtree of a node have values less than the current node.
2 > All the elements on the right subtree of a node have values greater than the current node.
3 > Performing inorder traversal on a Binary search tree will result in a sorted list.

Since we want to find the kth Smallest node, performing inorder traversal on the tree would make sense since we will get a sorted list and it will be easier to determine the kth smallest element.

Inorder travesal Algorithm

In Inorder traversal, we first process all nodes in left subtree of a node, then process the current node, then visit all the nodes in right subtree.

Visually :

Let's work on the next part ie determining the kth smallest element, one way could be to store all the node values in an array and determine the kth smallest, another space-saving way will be to keep a counter, keep on increasing it, and when the counter hit's k, return the node value.

Visually :

Converting coffee to code :

var kthSmallest = function(root, k) {
    let val;
    function inorder(root){
        if(root == null) {
            return;
        }

        inorder(root.left);
        k--;

        if(k == 0) {
            val = root.val;
            return;
        }

        inorder(root.right);
    }
    inorder(root);
    return val;
};

If you've made it till here, comment on the expected time complexities in the best case, the average case, and worst-case scenarios.

I hope you liked my explanation. If you know a better way then please share it with us :)

Github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/kthSmallestInaBST.js