Leetcode 509 Solution

This article provides solution to leetcode question 509 (inorder-successor-in-bst-ii)

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

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, node: 'Node') -> 'Optional[Node]':
        if node.right:
            p = node.right
            while p.left:
                p = p.left
            return p

        if node.parent:
            p = node
            while p.parent and p.parent.right == p:
                p = p.parent
            return p.parent

        return None