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).
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 result = null;
10
11 function inorder(node) {
12 if (!node) return;
13 inorder(node.left);
14 if (++count === k) {
15 result = node.val;
16 return;
17 }
18 inorder(node.right);
19 }
20
21 inorder(root);
22 return result;
23};This JavaScript solution operates recursively. A counter keeps track of the number of visited nodes during an in-order traversal. Once the kth node is visited, the counter matches k, and the result is set to the current node's value.
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).
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 TreeNode curr = root;
15 int count = 0;
16
17 while (curr != null) {
18 if (curr.left == null) {
19 count++;
20 if (count == k) return curr.val;
21 curr = curr.right;
22 } else {
23 TreeNode pre = curr.left;
24 while (pre.right != null && pre.right != curr) pre = pre.right;
25
26 if (pre.right == null) {
27 pre.right = curr;
28 curr = curr.left;
29 } else {
30 pre.right = null;
31 count++;
32 if (count == k) return curr.val;
33 curr = curr.right;
34 }
35 }
36 }
37 return -1; // This line is never reached if the tree contains the kth smallest element.
38 }
39}In C#, this approach adopts the Morris Traversal method for achieving the O(1) space complexity. This involves temporary modification of the tree structure to track nodes iteratively.