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&lt;TreeNode&gt; st = new Stack&lt;&gt;();

    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?
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.