Finding the Inorder Successor in a Binary Search Tree (BST)

Problem Description
Given a binary search tree (BST) and one of its nodes p, find the inorder successor of that node (i.e., the node that appears immediately after p in the inorder traversal sequence). It is assumed that each node contains a val (value), left (left child), right (right child), and parent pointer. If p has no successor, return null.

Solution Process

Step 1: Understanding Inorder Traversal and the Definition of a Successor

• The inorder traversal result of a binary search tree is an ascending ordered sequence.
• The successor node of p is the smallest node that appears after p in the inorder traversal.
• Example: For an inorder traversal [2, 3, 5, 7, 9], if p=5, the successor is 7; if p=9, the successor is null.

Step 2: Analyzing Possible Locations of the Successor Node
The location of the successor node falls into two cases:

1. p has a right subtree:

   • The successor is the leftmost node in p's right subtree (i.e., the minimum node in the right subtree).
   • Reason: After visiting p in an inorder traversal, the leftmost branch of its right subtree is traversed immediately.
   • Example: If p's right child is r, start from r and keep moving left until reaching a leaf node.

2. p has no right subtree:

   • The successor is an ancestor of p where this ancestor is the left child of its own parent.
   • Reason: After finishing visiting p, the traversal backtracks to the first ancestor whose "right subtree has not been processed."
   • Search method: Starting from p, traverse upwards until finding a node x such that p is located in the left subtree of x. This x is the successor.

Step 3: Algorithm Implementation

• If p.right != null:
  • Start from p.right and traverse leftwards continuously, returning the deepest left child node.
• If p.right == null:
  • Start from p and traverse upwards until finding a node x that satisfies the condition that p is the left child of x (i.e., x.left == p).
  • If the root is reached without finding such a node, it means p is the last node, so return null.

Step 4: Code Example (with Detailed Comments)

def find_inorder_successor(p):
    if not p:
        return None
    
    # Case 1: p has a right subtree
    if p.right:
        node = p.right
        while node.left:  # Find the leftmost node in the right subtree
            node = node.left
        return node
    
    # Case 2: p has no right subtree
    else:
        # Traverse upwards to find the first ancestor where p is in its left subtree
        node = p
        while node.parent and node.parent.right == node:
            node = node.parent  # If p is the right child of its parent, continue upwards
        return node.parent  # At this point, node's parent is the successor

Step 5: Example Verification
Take the following BST as an example (parent pointers are in parentheses):

       5 (null)
      / \
    3 (5)  8 (5)
   / \    / \
  2 (3) 6 (8) 9 (8)
     \    \
    4 (3)  7 (6)

• If p=4 (no right subtree): Move up to 3 (4 is the right child of 3), then continue up to 5 (3 is the left child of 5). The successor is 5.
• If p=5 (has a right subtree): Enter the right subtree 8, then move left to find 6. The successor is 6.
• If p=9 (no right subtree): Move up to 8 (9 is the right child of 8), then continue up to 5 (8 is the right child of 5). No qualifying ancestor is found, so return null.

Key Points Summary

• Using the parent pointer allows efficient backtracking to ancestor nodes. Without the parent pointer, the tree must be traversed from the root again (time complexity increases to O(n)).
• The algorithm has an average time complexity of O(log n), and O(n) in the worst case (when the tree degenerates into a linked list).