- naive approach:
- traverse the tree in any order
- push each element into a heap / priority queue
- after traversal, pop the queue k times and return the kth value
- requires O(n) auxillary space and added time complexity for consistent sorting
- optimization:
- the characteristics of a BST means that there is some semblance of order to its insertion of elements
- in-order traversal (left -> root -> right) visits elements in sorted order
💡 Explanation of Solution
- recursively traverse the tree (in-order)
- keep a counter to trakc how many elements have been visited
- when counter reaches k, return the current node's value
⌛ Complexity Analysis
Time Complexity: O(n)
- linear traversal of all nodes in-order
Space Complexity: O(n) worst case due to balance of tree and use of recursive calls in the stack
💻 Implementation of Solution
class Solution {public: int kthSmallest(TreeNode* root, int k) { int count = 0; int result = -1; inOrderTraversal(root, k, count, result); return result; }private: void inOrderTraversal(TreeNode* node, int k, int& count, int& result) { if(!node) return; //traverse the left subtree inOrderTraversal(node->left, k, count, result); //process the current node count++; if(count == k) { result = node->val; return; } //process the right subtree inOrderTraversal(node->right, k, count, result); }};