C++| Inorder Traversal using Recursion | With Example
Approach: \n1. First call recursion on the left subtree.\n2. Then increment the count by 1 (storing the position of that element when arranged in increasing ord
## **Approach:** \n1. First call recursion on the left subtree.\n2. Then increment the count by 1 (storing the position of that element when arranged in increasing order)\n3. If the count is equal to k, then we return that value. Else we recurse the right subtree.\n\n* If we come across a null node, return -1 so that we can differentiate the node values from null.\n* After traversing the left subtree, check whether the returned value is unequal to k. If yes, return the value. Else, traverse the right side.\n\n## **Example**\nFor a BST: [5,3,6,2,4,null,null,1] and k=4 the traversal would look like the following:\n![image](https://assets.leetcode.com/users/images/b17130b9-567a-423f-adbb-e7578190848d_1650283426.9845426.png)\n\n## **Code**\n```\nclass Solution {\npublic:\n    int c=0;\n    int kthSmallest(TreeNode* root, int k) {\n        if(!root)return -1;\n        int p=kthSmallest(root->left,k);\n        if(p!=-1)return p;\n        ++c;\n        if(c==k) return root->val;\n        return kthSmallest(root->right,k);\n    }\n};\n```\n**Time Complexity:** O(n) in worst case as we will traverse all the nodes once.\n**Space Complexity:** O(n) due the recursive stack.\n
[]