Write Infront
To read to tutorial, please to read the tutorial of inorder traversal of BST, please check:
LeetCode Solution 94: Binary Tree Inorder Traversal
We are going to solve this question using the following 4 methods:
>Binary Search
>Recursive
>Iterative
>Morris
Approach #1 Binary Search [Accepted]
Detail Explanation
The first method to solve this problem is using Binary Search.
The idea is very easy and extremely to think.
We use BST's property that the left child of the root is smaller than the root
while the right child of the root is always bigger.
We consider that the root is the pivot,
and find the number of the nodes in the left subtree
and the number of the nodes in the right subtree,
then go into the subtree that the Kth Smallest Value Node belongs to.
Java
class Solution {
public int kthSmallest(TreeNode root, int k) {
int counter = helper(root.left);
if(k<=counter)
{
return kthSmallest(root.left, k);
}
else if(k > counter+1)
{
return kthSmallest(root.right, k1counter);
}
return root.val;
}
public int helper(TreeNode root)
{
if(root == null) return 0;
return 1+helper(root.left)+helper(root.right);
}
}
Complexity Analysis

Time complexity : $$O(log(k))$$.

Space complexity : $$O(k)$$
Approach #2 Recursive [Accepted]
Detail Explaination
This is the classical method and straightforward. we can define a helper function to implement recursion.
The JAVA code is as follows:
Java
class Solution {
private static int counter;
private static int res;
public int kthSmallest(TreeNode root, int k) {
counter = k;
helper(root, k);
return res;
}
public void helper(TreeNode root, int k) {
if (root == null)
return;
if (root.left != null) {
helper(root.left, k);
}
counter;
if(counter == 0)
{
res = root.val;
return;
}
if (root.right != null) {
helper(root.right, k);
}
}
}
Complexity Analysis

Time complexity : $$O(k)$$.

Space complexity : $$O(k)$$.
Approach #3 Iterating method using Stack [Accepted]
Detail Explanation
The strategy is very similar to the iterative method in inorder traversal BST,
the only different is we have to use a counter to count the node we are visiting,
if it is the Kth node we poped from the stack, return.
Java
class Solution {
public int kthSmallest(TreeNode root, int k) {
int counter = 0;
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while(curr!=null!stack.isEmpty())
{
while(curr!= null)
{
stack.push(curr);
curr = curr.left;
}
curr = stack.pop(); counter ++;
if(counter == k)
{
return curr.val;
}
curr = curr.right;
}
return 0;
}
}
Complexity Analysis

Time complexity : $$O(k)$$.

Space complexity : $$O(k)$$.
Approach #4 Morris Traversal [Accepted]
Detail Explanation
This method we have to use a new data structure Threaded Binary Tree and the strategy is as follows:
Step1. Initialize current as root, counter is 0 and result as the min value;
Step2. While current is not NULL
If current does not have left child
a. counter++;
b. check the counter value, if the counter equals k, return.
c. Go to the right, i.e., current = current.right
Else
a. Denote pre as the left child of current node;
b. In current left subtree, make current right the right child of the rightmost node
c. If right most node do not have right child, we set its left child as current node, and update current to its left;
d. Else we set right most node right child as null, update and check counter, set current as its right.
For Example: k = 3
For more detail, please check
Threaded binary tree
Explain Morris Method
Java
class Solution {
public int kthSmallest(TreeNode root, int k) {
int counter = 0;
int res = Integer.MIN_VALUE;
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {
counter++;
if (counter == k) {
res = curr.val;
}
curr = curr.right;
} else {
TreeNode pre = curr.left;
while (pre.right != null && pre.right != curr) {
pre = pre.right;
}
if (pre.right == null) {
pre.right = curr;
curr = curr.left;
} else {
pre.right = null;
counter++;
if (counter == k)
res = curr.val;
curr = curr.right;
}
}
}
return res;
}
}
Complexity Analysis
 Time complexity : $$O(n)$$. To prove that the time complexity is $$O(n)$$,
the biggest problem lies in finding the time complexity of finding the predecessor nodes of all the nodes in the binary tree.
Intuitively, that complexity is $$O(nlgn)$$, because to find the predecessor node for a single node related to the height of the tree.
But in fact, finding the predecessor nodes for all nodes only needs $$O(n)$$ time. Because n nodes in a BinaryTree have n1 edges, the whole processing for each edges up to 2 times, one is to locate a node, and the other is to find the predecessor node.
So the complexity is $$O(n)$$.  Space complexity : $$O(1)$$. We only need pointer curr and pre.