285. Inorder Successor in BST - cocoder39/coco39_LC GitHub Wiki

285. Inorder Successor in BST

Notes 2020:

This option leverages in-order traversal. Suppose p is the kth smallest elements then time complexity is O(k), which is less efficient compared with other O(log N) approach(es).

class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        stack = []
        found = False
        cur = root
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            
            cur = stack.pop()
            if found:
                return cur
            if cur == p:
                found = True
            cur = cur.right
        return None

==================================================================================================

recursion. t(n) = 1 + t(n/2) = O(log n), space is O(h)

TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (! root) {
            return nullptr;
        } else if (root->val <= p->val) {
            return inorderSuccessor(root->right, p);
        } else { //root->val > p->val => root is a candidate
            TreeNode* node = inorderSuccessor(root->left, p);
            return node ? node : root;
        }
    }

closest nuber that is greater than p->val. Once found one node greater than p, we update res, go on checking if there existing closer node.

iteration, O(h) time and O(1) space

TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* res = nullptr;
        while (root) {
            if (root->val > p->val) {
                res = root;
                root = root->left;
            } 
            else {
                root = root->right;
            }
        }
        return res;
    }

follow up: there is parent node. Either going up or going down, time complexity is O(h), h = n for unbalanced bst

  • 1 if p has right subtree, min value of right subtree is successor
  • 2 else if p doesn't have parent, return nullptr
  • 3 else if p is left of p->parent, p->parent is successor
  • 4 else if p is right of p->parent, check step 2, 3 for p->parent
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (p->right) {
            TreeNode* res = p->right;
            while (res->left) {
                res = res->left;
            }
            return res;
        } else {
            while (p->parent && p != p->parent->left) {
                p = p->parent;
            }
            return p->parent;
        }
    }
⚠️ **GitHub.com Fallback** ⚠️