title: Returning Kth smallest element in a BST
body: <p>I wrote the following code snippet to return the <code>K</code>th smallest element in a BST:</p>
  
  <pre><code>/**
   * Definition for a binary tree node.
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   * };
   */
  
  class Solution {
  public:
  
      int kthSmallest(TreeNode* root, int k) {
          if(root==NULL)
              return -2;
          cout&lt;&lt;"Root value "&lt;&lt;root-&gt;val&lt;&lt;" and k value "&lt;&lt;k&lt;&lt;"\n";
  
          kthSmallest(root-&gt;left, k-1);
          if((k)==0)
              return root-&gt;val;
          kthSmallest(root-&gt;right, k-1);
      }
  };
  </code></pre>
  
  <p>I basically just do an inorder traversal of the tree and decrement the value of <code>k</code> during each recursive call.  So, in this way, when the value of <code>k</code> equals <code>0</code>, I have found the node and just return it.</p>
  
  <p>Following is the output of my debugging statements:</p>
  
  <blockquote>
    <p>Root value 1 and k value 3 <br>
    Root value 2 and k value 2 <br>
    Root value 4 and k value 1<br>
    Root value 8 and k value 0<br>
    Root value 9 and k value 0<br>
    Root value 5 and k value 1<br>
    Root value 10 and k value 0<br>
    Root value 11 and k value 0<br>
    Root value 3 and k value 2<br>
    Root value 6 and k value 1<br>
    Root value 12 and k value 0<br>
    Root value 7 and k value 1<br></p>
  </blockquote>
  
  <p>I am unable to understand why the program keeps on executing even after <code>k</code> has become <code>0</code>.  What have I missed?  I appreciate your help.   </p>
  
  <p><strong>Edit</strong>:  I don't think the question description is required, but if needed, it can be found here: <a href="https://leetcode.com/problems/kth-smallest-element-in-a-bst/#/description" rel="nofollow noreferrer">LeetCode: Find Kth smallest element in a BST</a>.  Also, please note that I cannot edit the function prototype.  Also, the question says that the <code>k</code> would be a valid number between <code>1</code> and BST's total number of elements.</p>