C++ concise 3 approaches : Recursive, Iterative and Binary Search


  • 0
    S

    Recursive Solution:
    Return INT_MAX if k > no of nodes in the subproblem.
    '''

    int kthSmallest(TreeNode* root, int k) {
        int cntr = k;
        return kthHelper(root,cntr);
    }
    int kthHelper(TreeNode * node, int &cntr){
        if(node == NULL) return INT_MAX;
        int t;
        t = kthHelper(node->left, cntr);
        if(t != INT_MAX) return t;
        cntr--;
        if(cntr == 0) return node->val;
        t = kthHelper(node->right, cntr);
        if(t != INT_MAX) return t;
        return INT_MAX;
    }
    

    '''

    Iterative Solution:
    Similar to iterative approach for in-order traversal, return INT_MAX if invalid k

    '''

    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode *> nodeStack;
        nodeStack.push(root);
        TreeNode * node = root;
        while(node->left){
            node = node->left;
            nodeStack.push(node);
        }
        int cntr = k;
        while(! nodeStack.empty()){
            node = nodeStack.top();
            cntr--;
            if(cntr == 0) return node->val;
            nodeStack.pop();
            if(node->right) {
                node = node->right;
                nodeStack.push(node);
                while(node->left){
                    node = node->left;
                    nodeStack.push(node);
                }
            }
        }
        return INT_MAX;
    }
    

    '''

    Binary Search Solution

    '''
    private:

    int countNodes(TreeNode * node){
        if(node == NULL) return 0;
        return 1 + countNodes(node->left) + countNodes(node->right);
    }
    

    public:

    int kthSmallest(TreeNode* root, int k) {
        int no_left = countNodes(root->left);
        if(no_left == k-1) return root->val;
        else if(no_left > k-1) return kthSmallest(root->left, k);
        else return kthSmallest(root->right, k-no_left-1);
    }
    

    '''


  • 0
    X

    Maybe you can use a map to cache the counts in the "Binary Search Solution", otherwise it would recalculate subtrees.


  • 0
    C

    What's your time complexity of the binary search solution? What about using memorization?


Log in to reply
 

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