DEV Community

loading...

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

akhilpokle profile image Akhil ・2 min read

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
Enter fullscreen mode Exit fullscreen mode

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 : Alt Text

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 : Alt Text

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;
};
Enter fullscreen mode Exit fullscreen mode

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

Discussion (2)

pic
Editor guide
Collapse
ayanb profile image
Ayan Banerjee • Edited

You can also perform iterative inorder traversal and improve the time complexity to O(H + K). For a balanced tree H = logN however, for a skewed tree, it can be H = N.

def kthSmallest(root, k):
    s = []  # stack
    while root != None or s:
        while root != None:
            s.append(root)
            root = root.left
        root = s[-1]
        s.pop()
        k -= 1
        if k == 0: return root.val
        root = root.right
Collapse
akhilpokle profile image
Akhil Author

Thanks for sharing :)