Inorder Successor in BST II

Problem Statement

In this problem, you're given a specific node from a binary search tree (BST) and asked to determine its in-order successor. The in-order successor of a node in a BST is defined as the node with the smallest key that is greater than the value of the given node (node.val). If the node does not have an in-order successor in the tree, the function should return null.

This task is unique because you only have access to the node itself and its parent, not to the root of the entire tree. The given node class structure (Node) includes the node's value (val), left child (left), right child (right), and the node's parent (parent).

Examples

Example 1

Input:

tree = [2,1,3], node = 1

Output:

2

Explanation:

1's in-order successor node is 2. Note that both the node and the return value is of Node type.

Example 2

Input:

tree = [5,3,6,2,4,null,null,1], node = 6

Output:

null

Explanation:

There is no in-order successor of the current node, so the answer is null.

Constraints

• The number of nodes in the tree is in the range [1, 104].
• -105 <= Node.val <= 105
• All Nodes will have unique values.

Approach and Intuition

Understanding how the in-order traversal works is key to solving this problem. During an in-order traversal of a BST, nodes are visited in a non-decreasing order of their values. When traversing in this manner, the successor of a node is the next node that gets visited.

Here's an intuition leading towards a solution:

1. If the node has a right child, the in-order successor is somewhere in the right subtree. To find it:

   • Move to the right child of the node.
   • Then, continually move to the leftmost child until there are no more left children. The node you stop at is the successor.

2. If the node does not have a right child, the in-order successor would be one of its ancestors, specifically the first parent for which the given node lies in the left subtree. To find this:

   • Move up to the parent of the node.
   • Continue moving up until you find a node that is the left child of its parent. The parent of this node is the in-order successor.

3. If neither of the above conditions is satisfied (no right child and no parent where the node is a left child), the node has no in-order successor, and you return null.

These steps leverage the properties of BSTs, where all values in a node's right subtree are greater than the node’s value, and all values in the left subtree are less. This allows for the efficient determination of the next higher value, which is what the in-order successor is.

Examples from the problem statement to illustrate the approach:

• Example 1: For the node with value 1 in a tree of 2, 1, 3; the node has no right child but is the left child of 2. Hence, its in-order successor is 2.
• Example 2: For the node with value 6, since it has no right child and it is not in the left subtree of any parent, it has no successor and thus returns null.

Solutions

class Solution {
public:
    Node* findInorderSuccessor(Node* node) {
        if (node->right) {
            node = node->right;
            while (node->left) node = node->left;
            return node;
        }
        
        while (node->parent && node == node->parent->right) node = node->parent;
        return node->parent;
    }
};

class Solution {
  public Node getNextInorder(Node node) {
    // Seek right then leftmost node
    if (node.right != null) {
      node = node.right;
      while (node.left != null) node = node.left;
      return node;
    }

    // Find the first left parent
    while (node.parent != null && node == node.parent.right) node = node.parent;
    return node.parent;
  }
}