LC 0510 [M] Inorder Successor in BST II - ALawliet/algorithms GitHub Wiki

naive solution

"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

class Solution:
    def inorderSuccessor(self, p: 'Node') -> 'Optional[Node]':
        # find root
        root = None
        cur = p
        while cur.parent:
            cur = cur.parent
        root = cur
        
        # inorder successor of p in BST given root
        self.successor = None
        def inorder(node):
            if not node: return None
            inorder(node.left)
            if node.val > p.val:
                if not self.successor or node.val < self.successor.val:
                    self.successor = node
            inorder(node.right)
        inorder(root)
        return self.successor

1. node has a right child, then its successor is its leftmost leaf node
2. node has no right child, then its successor must be the nearest ancestor who has it as a left child (thanks to BST property)
  successor
    /
node
3. no successor if none of the above two cases hold

class Solution:
    def inorderSuccessor(self, node: 'Node') -> 'Node':
        if node.right:
            node = node.right
            while node.left:
                node = node.left
            return node

        while node.parent: 
            if node.parent.left == node:
                return node.parent
            node = node.parent

        return None

alternative loop

while node.parent and node.parent.val < node.val:
    node = node.parent
return node.parent