C solutions comparing realloc (16ms) and fixed size (12ms) which is the best submission, instructive comments provided

  • 0
    #define LEN 100
    struct BSTIterator
        struct TreeNode** stack;
        int size;
    void collectLeft(struct TreeNode* root, struct BSTIterator* t)
        for(struct TreeNode* l=root; l; l=l->left)
            /*t->stack = (struct TreeNode**)realloc(t->stack, sizeof(struct TreeNode*)*(t->size+1));*/
            t->stack[(t->size)++] = l;
    //AC - 16ms; - using a fixed size is better in this case - removing realloc method;
    //AC - 12ms;
    struct BSTIterator* bstIteratorCreate(struct TreeNode* root)
        struct BSTIterator* t = (struct BSTIterator*)malloc(sizeof(struct BSTIterator));
        t->stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*LEN);
        t->size = 0;
        collectLeft(root, t);
        return t;
    bool bstIteratorHasNext(struct BSTIterator* iter)
        return iter->size;
    int bstIteratorNext(struct BSTIterator* iter)
        int ret = iter->stack[iter->size-1]->val;
        collectLeft(iter->stack[iter->size]->right, iter); //since the current node is being popped, collecting the next bigger part - its right children;
        return ret;
    void bstIteratorFree(struct BSTIterator* iter)

Log in to reply

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