Inorder Successor In Bst Ii - Leetcode Solution

Problem Description: Given a binary search tree (BST) and a node in it, find the in-order successor of that node in the BST. The successor of a node is the node with the smallest key greater than node.val.

Constraints:

1. The number of nodes in the tree is in the range [1, 10^4].
2. -10^8 <= Node.val <= 10^8
3. All Nodes values are unique.

Solution: In order to find the inorder successor of a node in a BST, we need to follow the below steps:

1. If the node has a right child, the inorder successor is the leftmost node of its right subtree. We can start from the right child and keep going to the left child until we reach the leftmost node.
2. If the node doesn't have a right child, then we need to find the ancestor of the node whose left child is also an ancestor of the node. We can start from the root and traverse through the tree until we find the node. If the node is in the left subtree of the ancestor, then the ancestor is the inorder successor. Otherwise, we keep going up until we find an ancestor whose left subtree contains the node.

Let's implement this approach using recursion:

class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        if not root:
            return None

        # If p has a right child
        if p.right:
            p = p.right
            while p.left:
                p = p.left
            return p

        # If p doesn't have a right child
        successor = None
        while root:
            if p.val < root.val:
                successor = root
                root = root.left
            elif p.val > root.val:
                root = root.right
            else:
                break

        return successor

Time Complexity: The time complexity of this algorithm is O(h), where h is the height of the tree. In the worst case, the tree is skewed, and the height is O(n). But in the average case, the height is O(log n), where n is the number of nodes in the tree.

Space Complexity: The space complexity of this algorithm is O(1), because we use only constant extra space to keep track of the current node and the successor.

1