Reference: LeetCode

Difficulty: Medium

My Post: Java Solution + Explanation (Recursion & Iteration)

## Problem

Given a binary search tree and a node in it, find the in-order successor of that node in the BST. The successor of a node

`p`

is the node with the smallest key greater than`p.val`

.

**Note:**

- If the given node has no in-order successor in the tree, return
`null`

. - It’s guaranteed that the values of the tree are
`unique`

.

**Example:**

1 | Input: root = [2,1,3], p = 1 |

## Analysis

**Methods:**

`x`

is the current node;`p`

is the target node.

- Recursion
- If
`p`

is in the left subtree, the successor could be`x`

or`successor(x.left)`

. It means that`x`

is a possible candidate. It turns to be a real successor when the return value of`successor(x.left)`

equals`null`

. - If
`p`

is in the right subtree, the successor must be in the right subtree if it exists. - If
`p`

is found, we still go to right subtree to find its successor if it exists. - The base case is when
`x`

reaches`null`

. **Time:**$O(h)$**Space:**$O(h)$

- If
- Iteration
- We use a variable
`succ`

to record the successor, which is initially`null`

. - If
`p.val`

is less than`x.val`

, it needs to go left, and we need to update`succ`

. - If
`p.val`

is greater than or equal to`x.val`

:`greater than`

: Just go right.`x.left`

and`x`

couldn’t be the successor.`equal to`

: Just go right too. In the next round,`p.val`

will be less than`x.val`

, it will set the`succ`

to the would-be right child`x`

.

**Time:**$O(h)$**Space:**$O(1)$

- We use a variable

## Code

**Test Case:**

1 | [2,1,3] p = 1 |

### Recursion

1 | public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { |

**Predecessor:**

1 | public TreeNode inorderPredecessor(TreeNode root, TreeNode p) { |

### Iteration

1 | public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { |

### Ceil

Code: algs4 - BST.java

The idea is also applied to `ceil`

operation:

1 | public Key ceil(Key key) { |

Comment