deepSWE.io

Inorder Successor in BST II

Trees

Problem Statement

Given a node in a binary search tree, 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`. Each node will have a reference to its parent node.

Example

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

Output: 2

Algorithm Explanation

This problem is similar to the previous one, but now each node has a pointer to its parent. This makes finding the successor easier in the case where the node has no right child.

Algorithm Steps

Case 1: Node has a right child. The successor is the leftmost node in the right subtree.
Case 2: Node has no right child. We go up the tree using the parent pointers until we find a node that is the left child of its parent. That parent is the successor. If we reach the root and haven't found such a node, then there is no successor.

Start

Finding successor of 1

Inorder Successor in BST II Solution


class Solution:
    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':
        # Case 1: Node has a right child
        if node.right:
            node = node.right
            while node.left:
                node = node.left
            return node
        
        # Case 2: Node has no right child
        while node.parent and node == node.parent.right:
            node = node.parent
        return node.parent