C 9ms recursive clean accepted solution


  • 0
    V

    Basically in-order traversal where you tell each node what element they would be if they were dumped into an array in-order (sorted).

    Requires extra space for an integer. Can be enhanced to stop recursion and rapidly return as soon as element k is found.

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
     
    int kHelper(struct TreeNode* node, int prevCount, int k, int* retVal) {
        if (node == NULL) return prevCount;
        int count = prevCount;
        count = kHelper(node->left, count, k, retVal);
        if (count == k) {
            *retVal = node->val;
        }
        return kHelper(node->right, count+1, k, retVal);
        
    }
    int kthSmallest(struct TreeNode* root, int k) {
        if (root == NULL) return 0;
        int* retVal = malloc(sizeof(int));
        kHelper(root, 1, k, retVal);
        return *retVal;
    }

Log in to reply
 

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