Inorder Successor in BST II

Problem Id: 510 Difficulty: Medium Tag: Tree


Intuition

If node.right is not None, then the successor is the smallest element in the right tree of the node.

If node.right is None, the successor is the lowest one of the node's ancestor where the node is on its left sub-tree.

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') -> 'Node':
        if node is None:
            return None

        if node.right is not None:
            smallest = node.right
            while smallest.left:
                smallest = smallest.left
        else:
            smallest = node.parent
            while smallest and smallest.right is node:
                node = smallest
                smallest = smallest.parent
        return smallest