#include <iostream>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int count = 0;
        int result = -1;
        kthSmallestHelper(root, k, count, result);
        return result;
    }

private:
    void kthSmallestHelper(TreeNode* node, int k, int& count, int& result) {
        if (node == nullptr) {
            return;
        }
        
        // Traverse the left subtree
        kthSmallestHelper(node->left, k, count, result);
        
        // Process the current node
        count++;
        if (count == k) {
            result = node->val;
            return;
        }
        
        // Traverse the right subtree
        kthSmallestHelper(node->right, k, count, result);
    }
};

int main() {
    TreeNode* root = new TreeNode(20);
    root->left = new TreeNode(10);
    root->right = new TreeNode(30);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(14);
    root->right->left = new TreeNode(25);
    root->right->right = new TreeNode(35);
    
    Solution solution;
    int k = 3;
    std::cout << "Kth smallest element for k = " << k << ": " << solution.kthSmallest(root, k) << std::endl;

    k = 5;
    std::cout << "Kth smallest element for k = " << k << ": " << solution.kthSmallest(root, k) << std::endl;

    // Clean up memory (you should ideally have a proper function to delete the tree)
    delete root->right->right;
    delete root->right->left;
    delete root->right;
    delete root->left->right;
    delete root->left->left;
    delete root->left;
    delete root;

    return 0;
}