# Find inorder successor/predecessor of given node in binary search tree

There are many applications like this where we need to find out **inorder successor or predecessor **of a node in binary search tree.
## What is inorder successor in binary search tree?

Inorder successor is node which will come after a node in inorder traversal of binary search tree. In other words, it would be the next larger element in BST.

**There are four cases:**

1. If there is a **right child** of the given node. In this case the smallest element in the right sub tree would be the inorder successor.

2. If node **does not have right sub tree** and if last turn was right, then the node where we took the last left turn will be the inorder successor.

3. If node **does not have right sub tree** and if last turn was *left turn*, parent of the node is inorder successor.

4. If the node is the **right most node**, then there is no inorder successor.

It is clear from the analysis that we need to change the candidate only when we are moving towards left and not when moving right.

Let’s see some examples:

In this in-order successor of 8 is 10.

Here, in-order successor of 12 is 14.

Here in-order successor of 4 is 6.

This is special case, where the node has right sub tree, then minimum element in the right sub tree is the in-order successor. In-order successor of 14 is 15. Similarly, In-order successor of 6 would be 8.

Notice something? Yes, in-order successor of a node is the node where we took latest left turn

For 8, we took left turn at 10, for 12 we did it at 14 and for 4, we did that at 6.

## Algorithm to find inorder successor

2. If the node is given has less than root, then search on left side and update successor.

3. If the node is greater than root, then search in right part, don’t update successor.

4. If we find the node and if the node has right sub tree, then the minimum node on the right sub tree of node is the in-order successor.

5. Return successor

## Code

### Complexity analysis

Complexity of algorithm to find *inorder successor* will be *O(logN)* in almost balanced binary tree. If tree is skewed, then we have worst case complexity of O(N).

## Inorder Predecessor in binary search tree (BST)

**Case 1: Node has left sub tree.**

In this case the right most node in the left sub-tree would be the inorder predecessor.

For example in above tree, in-order predecessor of 8 will be 6

**Case 2: Node has no left sub-tree.**

In this case in-order predecessor will be the node where we took the latest right turn.

In this example, in-order predecessor of 15 would be 14

In this example, in-order predecessor of 12 would be 10

Case 3 : Node is left most node of BST.

There is no in-order predecessor in this case and In this case there won’t be any right turn.

In this example, in-order predecessor of 6 will be NULL.

### Code

### Complexity analysis

Complexity of finding __inorder predecessor__ would be same as __inorder successor __i.e. O(logN).