# LeetCode 285: Inorder Successor in BST

## Problem Restatement

We are given the root of a binary search tree and a node `p` inside that tree.

We need to return the inorder successor of `p`.

In a binary search tree, inorder traversal visits nodes in sorted order.

So the inorder successor of `p` is the node with the smallest value greater than `p.val`.

If no such node exists, return `None`.

The source statement defines the successor as the node with the smallest key greater than `p.val`, and the return value is a `TreeNode`, not just the value.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `root` of a BST and a node `p` |
| Output | The successor `TreeNode`, or `None` |
| BST rule | Left subtree values are smaller, right subtree values are larger |
| Node values | Unique values |

Function shape:

```python
class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        ...
```

## Examples

For:

```python
root = [2, 1, 3]
p = 1
```

The inorder traversal is:

```python
1, 2, 3
```

The node after `1` is `2`.

So the answer is the node with value:

```python
2
```

For:

```python
root = [5, 3, 6, 2, 4, None, None, 1]
p = 6
```

The inorder traversal is:

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

There is no node after `6`.

So the answer is:

```python
None
```

## First Thought: Inorder Traversal

A direct solution is to perform inorder traversal and store the nodes in a list.

Because this is a BST, the list will be sorted by node value.

Then we find `p` in the list and return the next node.

```python
class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        nodes = []

        def inorder(node):
            if node is None:
                return

            inorder(node.left)
            nodes.append(node)
            inorder(node.right)

        inorder(root)

        for i in range(len(nodes)):
            if nodes[i] == p:
                if i + 1 < len(nodes):
                    return nodes[i + 1]
                return None

        return None
```

This is correct, but it visits every node and stores every node.

## Problem With Full Traversal

The BST property gives us more structure.

We do not need the full sorted list.

We only need the smallest node whose value is greater than `p.val`.

That means we can search the tree like binary search.

At each node:

- If `node.val > p.val`, this node may be the answer.
- If `node.val <= p.val`, this node cannot be the answer.

So we can walk down the tree while keeping the best candidate seen so far.

## Key Insight

The successor is:

```python
the smallest value greater than p.val
```

When we stand at a node `root`:

If:

```python
root.val > p.val
```

then `root` is a valid successor candidate.

But there might be a smaller valid node in `root.left`.

So we save `root` and move left.

If:

```python
root.val <= p.val
```

then `root` and everything in its left subtree are too small.

So we move right.

## Algorithm

Initialize:

```python
successor = None
```

Then walk down the tree.

While `root` exists:

1. If `root.val > p.val`, save `root` as a candidate and go left.
2. Otherwise, go right.

At the end, return `successor`.

## Correctness

The algorithm maintains `successor` as the best candidate seen so far: a node greater than `p.val`, with the smallest value among such nodes encountered on the search path.

When `root.val > p.val`, `root` is a valid successor candidate. Since a smaller valid successor may exist in the left subtree, the algorithm records `root` and searches left.

When `root.val <= p.val`, neither `root` nor any node in its left subtree can be the successor, because all of them have values at most `root.val`. The successor must be in the right subtree, so the algorithm searches right.

Every move discards only nodes that cannot improve the current answer. If a better candidate exists, the BST ordering keeps it on the path the algorithm follows.

When the search ends, no unexplored node can be a smaller valid successor than the stored candidate. Therefore `successor` is exactly the node with the smallest value greater than `p.val`, or `None` if no such node exists.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(h)` | We follow one root-to-leaf path |
| Space | `O(1)` | We store only one candidate |

Here, `h` is the height of the tree.

For a balanced tree, `h = O(log n)`.

For a skewed tree, `h = O(n)`.

## Implementation

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        successor = None

        while root:
            if root.val > p.val:
                successor = root
                root = root.left
            else:
                root = root.right

        return successor
```

## Code Explanation

We start with no candidate:

```python
successor = None
```

Then we search while the current node exists:

```python
while root:
```

If the current node is greater than `p`, it can be the successor:

```python
if root.val > p.val:
    successor = root
    root = root.left
```

We go left because we want a smaller value that is still greater than `p.val`.

Otherwise:

```python
else:
    root = root.right
```

The current node is too small, so we need larger values.

Finally:

```python
return successor
```

If `successor` was never updated, `p` has no inorder successor.

## Testing

```python
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def test_inorder_successor():
    s = Solution()

    root = TreeNode(2)
    root.left = TreeNode(1)
    root.right = TreeNode(3)

    assert s.inorderSuccessor(root, root.left).val == 2
    assert s.inorderSuccessor(root, root).val == 3
    assert s.inorderSuccessor(root, root.right) is None

    root2 = TreeNode(5)
    root2.left = TreeNode(3)
    root2.right = TreeNode(6)
    root2.left.left = TreeNode(2)
    root2.left.right = TreeNode(4)
    root2.left.left.left = TreeNode(1)

    assert s.inorderSuccessor(root2, root2.left).val == 4
    assert s.inorderSuccessor(root2, root2.left.right).val == 5
    assert s.inorderSuccessor(root2, root2.right) is None

    print("all tests passed")

test_inorder_successor()
```

Test meaning:

| Test | Why |
|---|---|
| `p = 1` in `[2,1,3]` | Successor is parent |
| `p = 2` in `[2,1,3]` | Successor is right child |
| `p = 3` in `[2,1,3]` | Largest node has no successor |
| `p = 3` in larger tree | Successor is inside right-side ordering |
| `p = 4` in larger tree | Successor is ancestor |
| `p = 6` in larger tree | No successor exists |