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 TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def kthSmallest(self, root: TreeNode, k: int) -> int:
9 def inorder(node):
10 if not node:
11 return []
12 return inorder(node.left) + [node.val] + inorder(node.right)
13
14 return inorder(root)[k - 1]This Python solution employs recursion to perform an in-order traversal, collecting node values in a list. The kth element is directly accessed by list indexing. This approach, however, uses O(n) space for storing the list.
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 <stdio.h>
2
3struct TreeNode {
4 int val;
5 struct TreeNode *left;
6 struct TreeNode *right;
7};
8
9int kthSmallest(struct TreeNode* root, int k) {
10 struct TreeNode* curr = root;
11 struct TreeNode* pre;
12 int count = 0;
13 int result;
14
15 while (curr != NULL) {
16 if (curr->left == NULL) {
17 if (++count == k) result = curr->val;
18 curr = curr->right;
19 } else {
20 pre = curr->left;
21 while (pre->right != NULL && pre->right != curr) pre = pre->right;
22
23 if (pre->right == NULL) {
24 pre->right = curr;
25 curr = curr->left;
26 } else {
27 pre->right = NULL;
28 if (++count == k) result = curr->val;
29 curr = curr->right;
30 }
31 }
32 }
33 return result;
34}This C implementation uses the Morris Traversal to avoid recursion. The traversal temporarily alters the tree's structure to keep track of each node's predecessor, thereby facilitating efficient space management.