# Find kth smallest element in binary search tree

I was faced with below interview question today and I came up with below solution but somehow interviewer was not happy. I am not sure why..

Given a binary search tree, find the kth smallest element in it.

Is there any better or more efficient way to do this problem?

  /*****************************************************
*
* Kth Smallest Iterative
*
******************************************************/

public int kthSmallestIterative(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.data;
TreeNode right = n.right;
while (right != null) {
st.push(right);
right = right.left;
}
}

return -1;
}


I mentioned time and space complexity as O(n). My iterative version takes extra space. Is there any way to do it without any extra space?

• Is the tree mutable? Is O(k) memory acceptable? – vnp Nov 29 '18 at 5:36
• I didn't asked this question to the interviewer but let's say if it is not mutable then can we optimize anything? And let's say if it is mutable then how efficiently we can do it? – user5447339 Nov 29 '18 at 5:57
• Do you have control over the TreeNode class? – tinstaafl Nov 29 '18 at 6:42
• If it is mutable, the Morris traversal is an answer. – vnp Nov 29 '18 at 16:08
• (Following proper specification and comments,) I guess I'd a) try to get hands on a capacity limited Deque b) push a dummy "super root" sr (root.clone()?) with sr.right = root, increase k and get rid of the duplicated push left-path. – greybeard Nov 29 '18 at 19:58

The "not happy interviewer" case is probably not connected to the efficiency of the algorithm, but to a few problems with the codes cleanliness:

• You modify method parameters. While this is technically possible, it is generally frowned upon as it makes code hard to read and even harder to debug. Don't do this. Period.
• Variable names don't match. root becomes a general pointer to a tree node (which is not root any more), right becomes left. This is a mumble jumble of hard to understand code, which is a nightmare to maintain.
• The way you find the target element is not obvious at a glance. At least add a comment on what you do and why it solves the original problem.

From the interviewers perspective, you managed to solve a simple problem with a piece of code, which already is problematic to understand and maintain. Imagine what happens if you get a real complex task with 100 classes and 10000 lines of code involved...

Thus: work on maintainability and clarity first.

• I agree with what you said, but would also add that this code (even if it's pseudocode) doesn't read like Java, which I would find concerning if I were interviewing someone who would be working primarily in Java – Katie.Sun Nov 29 '18 at 15:52

I mentioned time and space complexity as O(n).

Those bounds seem rather loose. If the tree is self-balancing then on a quick glance, and without attempting to prove it, I think your code probably has time complexity $$\O(k + \lg n)\$$ and space $$\O(\lg n)\$$.

My iterative version takes extra space. Is there any way to do it without any extra space?

Assuming that by "without any extra space" you really mean "with $$\O(1)\$$ extra space", it depends. Does TreeNode have a reference to its parent?

The way to really do this efficiently is for TreeNode to have a variable which tracks the size of the subtree rooted at that node.

• what if the tree is not self-balancing then what is the time and space complexity I have for my above code? So we cannot solve this without any extra space without modifying BST? – user5447339 Nov 29 '18 at 18:29
• [if balanced probable] time complexity O(k+lgn) or more generally $O(k+Height(T))$. – greybeard Nov 29 '18 at 19:35
• @user5447339: if the tree is not self-balancing then what is the time and space complexity [of] above code? You may need to go all the way down a tree without right nodes. You never need to go back more than k steps. $k \in O(n)$ (number of tree nodes - unknown) is generally presumed, but not guaranteed expressly. – greybeard Nov 29 '18 at 20:29