Problem statement

https://leetcode.com/problems/inorder-successor-in-bst-ii/

Solution

Similar to 0285 Inorder Successor in BST, but here we have access to parent node. If node have right children, go to it, and then go as left as possible. If node do not have right children, we need to go up, until the node is a left child, return the parent.

Complexity

Time complexity is O(h), space complexity is O(1).

Code

class Solution:
    def inorderSuccessor(self, node):
        if not node: return None
        res = None
        if node.right:
            res = node.right
            while res and res.left:
                res = res.left
        else:
            res = node.parent
            while res and res.val < node.val:
                res = res.parent

        return res