# Find Kth node 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.

Follow up: 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?

Solution 1: Inorder traversal

``````public class Solution {
public int kthSmallest(TreeNode root, int k) {
if (root == null || k <= 0) {
return -1;
}

Stack<TreeNode> stack = new Stack();

while (!stack.isEmpty() || root != null) {
if (root != null) {
stack.push(root);
root = root.left;
}
else {
root = stack.pop();
k--;
if (k == 0) {
return root.val;
}
root = root.right;
}
}

return -1;
}
}
``````

Followup: data structure

idea:

The idea is to maintain rank of each node. We can keep track of elements in a subtree of any node while building the tree. Since we need K-th smallest element, we can maintain number of elements of left subtree in every node.

Assume that the root is having N nodes in its left subtree. If K = N + 1, root is K-th node. If K < N, we will continue our search (recursion) for the Kth smallest element in the left subtree of root. If K > N + 1, we continue our search in the right subtree for the (K – N – 1)-th smallest element. Note that we need the count of elements in left subtree only.

Time complexity: O(h) where h is height of tree.

Algorithm:

``````start:
if K = root.leftElement + 1
root node is the K th node.
goto stop
else if K > root.leftElements
K = K - (root.leftElements + 1)
root = root.right
goto start
else
root = root.left
goto srart

stop:
``````