Find kth smallest element in binary search tree

Question

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?

Answer 1

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.

Answer 2

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.