Problem Statement
Pattern:
Iterative Inorder Traversal Solution
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new LinkedList<>();
while(root!=null || !stack.isEmpty()) {
if(root != null) {
stack.push(root);
root = root.left;
} else {
root = stack.pop();
if(k-- == 1) return root.val;
root = root.right;
}
}
return -1;
}Recursive Inorder Traversal Solution
int count = 0;
public int kthSmallest (TreeNode root, int k){
if(root == null) return -1;
int left = kthSmallest(root.left, k);
if(++count == k) return root.val;
int right = kthSmallest(root.right, k);
return (left != -1) ? left : right;
}