In a Binary Search Tree (BST), an in-order traversal visits nodes in ascending order. To find the kth smallest element, perform an in-order traversal and count the nodes until you reach the kth one.
Time Complexity: O(n), Space Complexity: O(n) (due to recursion stack in worst case).
1#include <vector>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11void inorder(TreeNode* node, int& k, int& result) {
12 if (!node || k <= 0) return;
13 inorder(node->left, k, result);
14 if (--k == 0) {
15 result = node->val;
16 return;
17 }
18 inorder(node->right, k, result);
19}
20
21int kthSmallest(TreeNode* root, int k) {
22 int result = -1;
23 inorder(root, k, result);
24 return result;
25}This C++ solution mirrors the recursive in-order strategy, using a reference to modify k and result in each recursive call, which allows the traversal to stop early once the kth smallest element is found.
Morris Traversal is a way to perform in-order traversal with O(1) extra space. This method modifies the tree's structure temporarily to avoid the recursive call stack. This approach uses the concept of threading where leaf nodes point to their in-order successor to facilitate traversal.
Time Complexity: O(n), Space Complexity: O(1).
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val)
3 this.left = (left===undefined ? null : left)
4 this.right = (right===undefined ? null : right)
5}
6
7var kthSmallest = function(root, k) {
8 let count = 0;
9 let current = root;
10 let result = null;
11
12 while (current) {
13 if (!current.left) {
14 count++;
15 if (count === k) return current.val;
16 current = current.right;
17 } else {
18 let predecessor = current.left;
19 while (predecessor.right && predecessor.right !== current) {
20 predecessor = predecessor.right;
21 }
22 if (!predecessor.right) {
23 predecessor.right = current;
24 current = current.left;
25 } else {
26 predecessor.right = null;
27 count++;
28 if (count === k) return current.val;
29 current = current.right;
30 }
31 }
32 }
33};The JavaScript implementation performs a Morris Traversal to achieve the traversal in constant space with no use of additional data structures such as stacks or recursion.