deepSWE.io

Inorder Successor in BST

Trees

Problem Statement

Given the `root` of a binary search tree and a node `p` in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return `null`.

Example

Input: root = [2,1,3], p = 1

Output: 2

Algorithm Explanation

There are two cases to consider when finding the in-order successor of a node `p`.

Algorithm Steps

Case 1: Node `p` has a right child. In this case, the in-order successor is the smallest node in `p`'s right subtree. We can find this by traversing down the left children of `p.right`.
Case 2: Node `p` has no right child. In this case, the in-order successor is one of `p`'s ancestors. We traverse up from `p` until we find a node that is the left child of its parent. That parent is the successor. A simpler way to implement this is to traverse from the root. While traversing, if we go left, the current node is a potential successor. If we go right, it's not.

Start

Finding successor of 1

Inorder Successor in BST Solution


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