Two different c++ solution, one is iterative, 24ms, and the other is recursive, 20ms.


  • 1

    For BST, the inorder traversal of its nodes' values is ascending. So we can solve this problem share the same idea with Binary Tree Inorder Traversal. The different is no need to traverse all nodes in this problem, and just traverse k times is ok.

    Here is my two different c++ solution:

    1.Iterative solution using stack, O(n) time and O(n) space, 24ms:

    class Solution {
    public:
        int kthSmallest(TreeNode* root, int k) {
            std::stack<TreeNode*> nodes;
            while (root || !nodes.empty())
                if (root) {
                    nodes.push(root);
                    root = root->left;
                }
                else {
                    root = nodes.top();
                    nodes.pop();
                    if (--k == 0)
                        return root->val;
                    root = root->right;
                }
        }
    };
    

    2.Recursive solution, O(n) time and O(1) space, 20ms:

    class Solution {
    public:
        int kthSmallest(TreeNode* root, int k) {
    		int res;
    		kthSmallestHelper(root, k, res);
    		return res;
        }
    private:
        void kthSmallestHelper(TreeNode* root, int &k, int &res) {
    	    if (k > 0 && root->left)
    		    kthSmallestHelper(root->left, k, res);
    	    if (--k == 0) {
    		    res = root->val;
    		    return;
    	    }
    	    if (k > 0 && root->right)
    		    kthSmallestHelper(root->right, k, res);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.