BiruLyu
8/5/2017 - 5:03 AM

## 230. Kth Smallest Element in a BST(#recursive).java

``````/*In order traverse for BST gives the natural order of numbers. No need to use array.*/

/*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);
}

/*Iterative:*/

public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
int count = 0;

while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);  // Just like recursion
p = p.left;

} else {
TreeNode node = stack.pop();
if(++count == k) return node.val;
p = node.right;
}
}

return Integer.MIN_VALUE;
}``````
``````  public int kthSmallest(TreeNode root, int k) {
int count = countNodes(root.left);
if (k <= count) {
return kthSmallest(root.left, k);
} else if (k > count + 1) {
return kthSmallest(root.right, k-1-count); // 1 is counted as current node
}

return root.val;
}

public int countNodes(TreeNode n) {
if (n == null) return 0;

return 1 + countNodes(n.left) + countNodes(n.right);
}``````
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private void inOrder(TreeNode root, int[] k) {
if (root == null) return;
inOrder(root.left, k);
if (--k[0] == 0) {
k[1] = root.val;
}
inOrder(root.right, k);
}
public int kthSmallest(TreeNode root, int k) {
int[] res = new int[2];
res[0] = k;
inOrder(root, res);
return res[1];
}
}``````