Problem statement

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

Solution

The idea is to use properties of BST. See more general problem 0272 Closest Binary Search Tree Value II. Idea is the following: we need to keep stack of left children in the path from root to our node. In the end return the last element of stack. In fact no need to keep stack, just the last one is enough.

Complexity

Time complexity for unbalanced trees it can be $O(n)$, for balanced it is just $O(\log n)$, space complexity is $O(1)$.

Code

class Solution:
    def inorderSuccessor(self, root, p):
        successor = None
        node = root
                
        while node:
            if node.val <= p.val:
                node = node.right
            else:
                successor = node
                node = node.left
        
        return successor