Problem Link: https://binarysearch.com/problems/Kth-Smallest-in-a-Binary-Search-Tree
Hello! Today we’ll be looking at how to find the kth smallest(0-indexed) in a BST. Well, how to approach this problem? First, notice that Binary Search Tree(BST) is a special form of binary tree in which a node’s left children have smaller values than its value and the right children have greater values than the node’s. Understanding this property of BST, we can further our thinking process to “how to print nodes in an ascending order?”. Congratulations to those of you have already come up with an idea!
In-order traversal in a BST will give nodes in an ascending order since for every node, nodes in its left sub-tree have smaller values and it’s the opposite for the right sub-tree.
In-order Traversal
But what if this is not a BST but just any tree? In this case, it might be good to consider “priority queue”. As we store values in a descending order in pq, we can always maintain kth largest(or smallest) value.
