Problem URL: Inorder successor in BST

As we are traversing a binary search tree, we can use it's property to find the inorder successor. The inorder successor of a node is the leftmost node in the right subtree. If the node does not have a right subtree, then the inorder successor is the lowest ancestor of the node whose left child is also an ancestor of the node.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
        successor = None
        while root:
            if p.val >= root.val:
                root = root.right
            else:
                successor = root
                root = root.left
        return successor

Time complexity: O(h), h is the height of the tree
Space complexity: O(1)