Quite standard in-order traversal recursive C++ solution


  • 0
    D

    Just do in-order traversal recursively, use k to track how many nodes it still needs to visit. Everytime, you visit a node, decrease k by one, if k reaches 0, return the current node value. worst case O(N) space, O(N) time.
    If there is a space limit, then use Morris traversal method to achieve O(1) space.

    For the follow-up question, for each node, include two new fields to save the number of nodes of its left subtree and right subtree, so we can do binary search.

        class Solution {
        private:
            bool inOrder(TreeNode* root, int &k, int &res)
            {
                if(!root) return false; 
    // if we found the k-th entry in the left subtree, then return
                if(inOrder(root->left, k, res)) return true;
    // otherwise, visit the current node, if it is the k-th node, just return with true
                if(!--k)
                {
                    res = root->val;
                    return true;
                }
    //otherwise, traverse the right subtree
                return inOrder(root->right, k, res);
            }
        public:
            int kthSmallest(TreeNode* root, int k) {
                int res;
                inOrder(root, k, res);
                return res;
            }
        };

Log in to reply
 

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