Kth Smallest Element in a BST
Credit to leetcode.com, this is a fun problem that with some understanding of the data structure (Binary Search Trees) can be solved relatively straightforward. Here it is: Given a binary search tree, write a function kthSmallest to find the k th smallest element in it. Note: You may assume k is always valid, 1 ≤ k ≤ BST's total elements. The key insight is that if you traverse an BST using an in-order method, the elements of the tree will be, as the name implies, in-order, that is, they will be already sorted. Remember the 3 basic traversal orders: Pre-Order: Process current node Process left node Process right node Post-Order: Process the left node Process the right node Process the current node In-Order: Process the left node Process the current node Process the right node So for this problem we'll traverse the tree in-order keeping a counter whenever we process the current node. The moment the counter gets to "k", we have found our e