Locating successor node with stack in kO(h) Time Complexity


  • 0
    L
    class Solution {
        public:
        int kthSmallest(TreeNode* root, int k) {
            stack<TreeNode*> stack;
            
            while (root->left != NULL) {
                stack.push(root);
                root = root->left;
            }
            
            TreeNode* ptr = root;
            
            while (--k) {
                ptr = successor(stack, ptr);
            }
            
            return ptr->val;
        }
        
        TreeNode* successor(stack<TreeNode*>& pS, TreeNode* ptr) {
            if (ptr->right != NULL)
                return minimum(pS, ptr->right);
                
            TreeNode* y = pS.top();
            pS.pop();
            
            while (ptr == y->right) {
                ptr = y;
                y = pS.top();
                pS.pop();
            }
            
            return y;
        }
        
        TreeNode* minimum(stack<TreeNode*>& pS, TreeNode* ptr) {
            while (ptr->left != NULL) {
                pS.push(ptr);
                ptr = ptr->left;
            }
            return ptr;
        }
    };

Log in to reply
 

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