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).
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
6 this.val = val;
7 this.left = left;
8 this.right = right;
9 }
10}
11
12public class Solution {
13 public int KthSmallest(TreeNode root, int k) {
14 int result = 0;
15 InOrder(root, ref k, ref result);
16 return result;
17 }
18
19 private void InOrder(TreeNode node, ref int k, ref int result) {
20 if (node == null) return;
21 InOrder(node.left, ref k, ref result);
22 if (--k == 0) {
23 result = node.val;
24 return;
25 }
26 InOrder(node.right, ref k, ref result);
27 }
28}In C#, we use reference parameters to manage the state (k and result) throughout the recursive calls. The InOrder method navigates the tree recursively while decrementing k until it finds the kth smallest element.
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).
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 TreeNode curr = root;
10 int count = 0;
11 int result = 0;
12
13 while (curr != null) {
14 if (curr.left == null) {
15 if (++count == k) result = curr.val;
16 curr = curr.right;
17 } else {
18 TreeNode pre = curr.left;
19 while (pre.right != null && pre.right != curr) pre = pre.right;
20
21 if (pre.right == null) {
22 pre.right = curr;
23 curr = curr.left;
24 } else {
25 pre.right = null;
26 if (++count == k) result = curr.val;
27 curr = curr.right;
28 }
29 }
30 }
31 return result;
32 }
33}This Java implementation leverages Morris Traversal to iterate through the tree without using a stack or recursion. It establishes temporary right pointers to predecessors to navigate efficiently.