## Thursday, November 24, 2016

### LeetCode 230 - Find k-th smallest element in BST

Related: Find k-th smallest element in BST
Second largest element in BST
https://leetcode.com/problems/kth-smallest-element-in-a-bst/
Given a binary search tree, write a function `kthSmallest` to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
X. DFS
The number of nodes (n) in the tree is irrelevant to the complexity. My code inorder traverse the tree and it stops when it finds the Kth node. The time complexity for this code is O(k).
The number of nodes in the tree does change the time complexity. The program actually goes to the left bottom node first and start from there to search for the Kth smallest. Thus the time complexity should be O(log(n) + K). What do you think ?
The time complexity is O(log(n) + K) only if the tree is balanced. In the worst-case scenario the tree can have a height of n, thus the time complexity could be O(n)
``````public int kthSmallest(TreeNode root, int k) {
ArrayList<Integer> buffer = new ArrayList<Integer>();
inorderSearch(root, buffer, k);
return buffer.get(k-1);
}
public void inorderSearch(TreeNode node, ArrayList<Integer> buffer, int k){
if(buffer.size() >= k)
return;
if(node.left != null){
inorderSearch(node.left, buffer, k);
}
if(node.right != null){
inorderSearch(node.right, buffer, k);
}
}``````
``````    public int kthSmallest(TreeNode root, int k) {

Stack<TreeNode> stack=new Stack<TreeNode>();
int c=0;
TreeNode cur=root;
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
while(!stack.isEmpty()){
TreeNode ptr=stack.pop();
c++;
if(c==k)return ptr.val;
TreeNode rt=ptr.right;
while(rt!=null){
stack.push(rt);
rt=rt.left;
}
}
return 0;
}``````
https://discuss.leetcode.com/topic/17810/3-ways-implemented-in-java-python-binary-search-in-order-iterative-recursive
``````int count = 0;
int result = Integer.MIN_VALUE;

public int kthSmallest(TreeNode root, int k) {
traverse(root, k);
return result;
}

public void traverse(TreeNode root, int k) {
if(root == null) return;
traverse(root.left, k);
count ++;
if(count == k) result = root.val;
traverse(root.right, k);
}``````

https://discuss.leetcode.com/topic/28910/two-easiest-in-order-traverse-java
https://discuss.leetcode.com/topic/17810/3-ways-implemented-in-java-binary-search-in-order-iterative-recursive
DFS in-order recursive:
``````    // better keep these two variables in a wrapper class
private static int number = 0;
private static int count = 0;

public int kthSmallest(TreeNode root, int k) {
count = k;
helper(root);
return number;
}

public void helper(TreeNode n) {
if (n.left != null) helper(n.left);
count--;
if (count == 0) {
number = n.val;
return;
}
if (n.right != null) helper(n.right);
}``````
X. DFS in-order iterative:
``````  public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> st = new Stack<>();

while (root != null) {
st.push(root);
root = root.left;
}

while (k != 0) {
TreeNode n = st.pop();
k--;
if (k == 0) return n.val;
TreeNode right = n.right;
while (right != null) {
st.push(right);
right = right.left;
}
}

return -1; // never hit if k is valid
}``````

https://discuss.leetcode.com/topic/46008/iterative-in-order-traversal-using-stack-java-solution
As a lot of us know, this question can be solved by in-order traversal. Here, I am going to show how you can solve this question easily by performing iterative in-order traversal using stack.
Code below is the iterative inorder traversal solution. It is pretty straightforward though, so I am not going to explain the code.
``````public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.empty()){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
root = root.right;

}
return list;
}
``````
Here, we can solve the finding kth smallest element with as little tweak as possible.
`````` public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()) {
while(root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if(--k == 0) break;
root = root.right;
}
return root.val;
}``````
https://discuss.leetcode.com/topic/17668/what-if-you-could-modify-the-bst-node-s-structure/2
If we could add a count field in the BST node class, it will take O(n) time when we calculate the count value for the whole tree, but after that, it will take O(logn) time when insert/delete a node or calculate the kth smallest element.
``````        public int kthSmallest(TreeNode root, int k) {
TreeNodeWithCount rootWithCount = buildTreeWithCount(root);
return kthSmallest(rootWithCount, k);
}

private TreeNodeWithCount buildTreeWithCount(TreeNode root) {
if (root == null) return null;
TreeNodeWithCount rootWithCount = new TreeNodeWithCount(root.val);
rootWithCount.left = buildTreeWithCount(root.left);
rootWithCount.right = buildTreeWithCount(root.right);
if (rootWithCount.left != null) rootWithCount.count += rootWithCount.left.count;
if (rootWithCount.right != null) rootWithCount.count += rootWithCount.right.count;
return rootWithCount;
}

private int kthSmallest(TreeNodeWithCount rootWithCount, int k) {
if (k <= 0 || k > rootWithCount.count) return -1;
if (rootWithCount.left != null) {
if (rootWithCount.left.count >= k) return kthSmallest(rootWithCount.left, k);
if (rootWithCount.left.count == k-1) return rootWithCount.val;
return kthSmallest(rootWithCount.right, k-1-rootWithCount.left.count);
} else {
if (k == 1) return rootWithCount.val;
return kthSmallest(rootWithCount.right, k-1);
}
}

class TreeNodeWithCount {
int val;
int count;
TreeNodeWithCount left;
TreeNodeWithCount right;
TreeNodeWithCount(int x) {val = x; count = 1;};
}``````

```记当前节点为node

```