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).
1class Solution {
2 static class TreeNode {
3 int val;
4 TreeNode left, right;
5 TreeNode(int x) { val = x; }
6 }
7
8 public int kthSmallest(TreeNode root, int k) {
9 int[] result = new int[2];
10 inorder(root, result, k);
11 return result[1];
12 }
13
14 private void inorder(TreeNode node, int[] result, int k) {
15 if (node == null) return;
16 inorder(node.left, result, k);
17 if (++result[0] == k) {
18 result[1] = node.val;
19 return;
20 }
21 inorder(node.right, result, k);
22 }
23}In this Java solution, an integer array is used to hold the count and the result concurrently. The traversal is stopped once the kth smallest element is found by updating the result array.
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).
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10int kthSmallest(TreeNode* root, int k) {
11 TreeNode* curr = root;
12 TreeNode* pre = nullptr;
13 int count = 0;
14 int result = 0;
15
16 while (curr) {
17 if (!curr->left) {
18 if (++count == k) result = curr->val;
19 curr = curr->right;
20 } else {
21 pre = curr->left;
22 while (pre->right && pre->right != curr) pre = pre->right;
23
24 if (!pre->right) {
25 pre->right = curr;
26 curr = curr->left;
27 } else {
28 pre->right = nullptr;
29 if (++count == k) result = curr->val;
30 curr = curr->right;
31 }
32 }
33 }
34
35 return result;
36}In this C++ code, we use Morris In-Order Traversal to accomplish the task in O(1) space. By establishing back-links from nodes to their in-order successor temporarily, we can traverse the tree without using the function call stack.