Simple C++ solution with explanation in inline comments.


  • 2
    I
    class Solution {
    public:
        int visit(TreeNode* root, int &k) {
            
            // if there are left children... 
            if (root->left)
            {
                // ... then the k'th smallest is somewhere to the left
                int res = visit(root->left,k);
                
                // ... if we don't need to go for the next smallest
                if (k == 1)
                    // then we are done
                    return res;
                // otherwise we go for the next smallest
                else k=k-1;
            }
    
            // if we don't need to go for the next smallest
            if (k == 1)
                // then we are the one
                return root->val;
            else
            {
                // otherwise, it's bigger than us, somewhere to the right.
                if (root->right)
                    {
                        k = k-1;
                        return visit(root->right, k);
                    }
            }
    
        }
    
        int kthSmallest(TreeNode* root, int k) {
            return visit(root, k);
        }
        
    };

Log in to reply
 

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