510. Inorder Successor in BST II - Detailed Explanation

Problem Statement

You are given a node in a binary search tree (BST) where each node has pointers not only to its left and right children but also to its parent. The task is to find the inorder successor of that node. The inorder successor is the node with the smallest key greater than the key of the given node when the BST is traversed in inorder (left, root, right).

Example 1

Consider the BST:

        20
       /  \
      10   30
     /  \
    5    15

• Input: Node with value 10
• Output: Node with value 15
• Explanation: In the inorder traversal of the tree, the sequence is [5, 10, 15, 20, 30]. The node after 10 is 15.

Example 2

Consider the same BST:

        20
       /  \
      10   30
     /  \
    5    15

• Input: Node with value 15
• Output: Node with value 20
• Explanation: The inorder sequence is [5, 10, 15, 20, 30]. The node after 15 is 20.

Example 3

Consider the same BST:

        20
       /  \
      10   30
     /  \
    5    15

• Input: Node with value 30
• Output: null
• Explanation: The inorder sequence is [5, 10, 15, 20, 30]. Since 30 is the last node in this order, it does not have an inorder successor.

Constraints

• Each node contains an integer value, and pointers to its left child, right child, and parent.
• The given node is guaranteed to be a valid node in the BST.
• If there is no inorder successor, return null.

Hints

1. Right Subtree Case:
   If the given node has a right child, the inorder successor is the leftmost node in the right subtree.
2. No Right Subtree Case:
   If the given node does not have a right child, move up the tree using the parent pointer until you find a node that is the left child of its parent. The parent of that node is the inorder successor.

Approaches Overview

Approach 1: Using the Right Subtree

• When to Use:
  If the node has a right child, this approach is straightforward.
• How it Works:
  • Move to the right child.
  • Then traverse left down the subtree until no more left children are found.
  • The last node reached is the inorder successor.
• Complexity:
  Time complexity is O(h), where h is the height of the tree.

Approach 2: Moving Up Through Parent Pointers

• When to Use:
  When the node does not have a right child.
• How it Works:
  • Start at the given node and move upward using the parent pointer.
  • Continue until you find a node that is the left child of its parent.
  • The parent of this node is the inorder successor.
  • If you reach the root without finding such a condition, the node is the rightmost node, so there is no inorder successor.
• Complexity:
  Again, the worst-case time complexity is O(h).

Detailed Step-by-Step Explanation

1. Check for Right Child:

   • If the node has a right child, go to that right child and then keep moving to its left child until you cannot go any further. This is because in a BST, the leftmost node in a subtree will have the smallest value in that subtree.

2. Move Up if No Right Child:

   • If the node does not have a right child, you must look upward.
   • Traverse up using the parent pointer until you find a node that is a left child of its parent. This indicates that the parent node's value is the next larger value.
   • If you cannot find such a node, it means the given node is the rightmost node in the BST, so return null.

3. Edge Cases:

   • If the given node is null, simply return null.
   • If the given node is the maximum node in the BST (i.e., no successor exists), return null.

Python Implementation