# LeetCode 510: Inorder Successor in BST II

## Problem Restatement

We are given a node in a binary search tree.

Each node contains:

| Field | Meaning |
|---|---|
| `val` | Node value |
| `left` | Left child |
| `right` | Right child |
| `parent` | Parent pointer |

We need to return the inorder successor of the given node.

The inorder successor of a node is the next node visited during inorder traversal:

```text
left -> root -> right
```

If no successor exists, return `None`.

The official problem provides parent pointers and asks for the next node in inorder traversal order. ([leetcode.com](https://leetcode.com/problems/inorder-successor-in-bst-ii/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | A node inside a BST |
| Output | The inorder successor node |
| Return `None` | If no successor exists |

Function shape:

```python
class Solution:
    def inorderSuccessor(self, node: 'Node') -> 'Optional[Node]':
        ...
```

## Examples

Example 1:

```text
      5
     / \
    3   6
   / \
  2   4
 /
1
```

Suppose the input node is:

```text
3
```

The inorder traversal is:

```text
1, 2, 3, 4, 5, 6
```

The next node after `3` is:

```text
4
```

So the answer is node `4`.

Example 2:

```text
      2
     / \
    1   3
```

If the input node is:

```text
3
```

then `3` is the final node in inorder traversal.

So the answer is:

```python
None
```

## First Thought: Build the Entire Inorder Traversal

One possible solution is:

1. Find the tree root.
2. Perform full inorder traversal.
3. Store nodes in an array.
4. Locate the target node.
5. Return the next array element.

This works, but it uses unnecessary extra memory.

The parent pointer gives us enough information to move upward directly.

## Key Insight

There are only two cases.

### Case 1: The node has a right subtree

If the node has a right child, then the successor is:

```text
the leftmost node in the right subtree
```

Example:

```text
    5
     \
      8
     /
    6
```

The successor of `5` is `6`.

We move right once, then go left as far as possible.

### Case 2: The node has no right subtree

Then we move upward using parent pointers.

We continue climbing while the current node is the right child of its parent.

The first parent where we arrive from the left side is the successor.

Example:

```text
      5
     /
    3
     \
      4
```

The successor of `4` is `5`.

We move upward from `4`.

`4` is a right child of `3`, so continue upward.

`3` is a left child of `5`, so `5` is the successor.

## Algorithm

If the node has a right child:

1. Move to `node.right`
2. Continue moving left until no left child exists
3. Return that node

Otherwise:

1. While:
   - `node.parent` exists
   - and `node` is the right child of its parent
2. Move upward
3. Return `node.parent`

If we reach the top without finding such a parent, return `None`.

## Correctness

Inorder traversal visits nodes in this order:

```text
left subtree -> node -> right subtree
```

If a node has a right subtree, the next visited node must be the leftmost node inside that right subtree. No smaller node there can appear after the current node.

If a node does not have a right subtree, then its successor must lie among its ancestors.

Moving upward from a right child means the ancestor and its left subtree have already been fully visited, so traversal continues upward.

The first ancestor reached from the left side is the first node whose inorder visit occurs after the current node.

If no such ancestor exists, then the current node is the rightmost node in the BST and has no inorder successor.

Therefore the algorithm always returns the correct inorder successor or `None`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(h)` | At most one upward or downward path |
| Space | `O(1)` | No recursion or extra data structures |

Here:

```text
h = tree height
```

## Implementation

```python
# Definition for a Node.
# class Node:
#     def __init__(self, val):
#         self.val = val
#         self.left = None
#         self.right = None
#         self.parent = None

class Solution:
    def inorderSuccessor(self, node: 'Node') -> 'Node':
        # Case 1:
        # Right subtree exists
        if node.right:
            current = node.right

            while current.left:
                current = current.left

            return current

        # Case 2:
        # Move upward
        while node.parent and node == node.parent.right:
            node = node.parent

        return node.parent
```

## Code Explanation

First check whether the node has a right subtree:

```python
if node.right:
```

If it does, move right once:

```python
current = node.right
```

Then move left as far as possible:

```python
while current.left:
    current = current.left
```

The leftmost node is the inorder successor.

If no right subtree exists, move upward:

```python
while node.parent and node == node.parent.right:
```

As long as the current node is a right child, its parent has already been visited during inorder traversal.

So continue climbing upward:

```python
node = node.parent
```

When the loop stops:

```python
return node.parent
```

returns the first ancestor reached from the left side.

If no such ancestor exists, `node.parent` is `None`.

## Testing

```python
def connect(parent, left=None, right=None):
    parent.left = left
    parent.right = right

    if left:
        left.parent = parent

    if right:
        right.parent = parent

def test_inorder_successor():
    s = Solution()

    # Tree:
    #       5
    #      / \
    #     3   6
    #    / \
    #   2   4
    #  /
    # 1

    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n4 = Node(4)
    n5 = Node(5)
    n6 = Node(6)

    connect(n5, n3, n6)
    connect(n3, n2, n4)
    connect(n2, n1)

    assert s.inorderSuccessor(n3).val == 4
    assert s.inorderSuccessor(n4).val == 5
    assert s.inorderSuccessor(n1).val == 2
    assert s.inorderSuccessor(n6) is None

    print("all tests passed")
```

Test meaning:

| Test | Why |
|---|---|
| Node with right subtree | Uses leftmost-right-subtree rule |
| Node without right subtree | Uses upward traversal |
| Small leftmost node | Simple successor case |
| Largest node | No successor exists |