Inorder Successor in BST II Python Solution

lcpy gen -n 510   # by problem number
lcpy gen -s inorder_successor_in_bst_ii   # by problem name

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

Input: tree = [2,1,3], node = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both the node and the return value is of Node type.

Input: tree = [5,3,6,2,4,null,null,1], node = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

from __future__ import annotations


class Node:
    def __init__(self, val: int = 0) -> None:
        self.val = val
        self.left: Node | None = None
        self.right: Node | None = None
        self.parent: Node | None = None


class Solution:
    # Time: O(h)
    # Space: O(1)
    def inorder_successor(self, node: Node) -> Node | None:
        if node.right is not None:
            succ = node.right
            while succ.left is not None:
                succ = succ.left
            return succ
        child = node
        parent = node.parent
        while parent is not None and parent.right is child:
            child = parent
            parent = parent.parent
        return parent