To find the in-order successor of a node, we need to look very closely as how inorder traverse works on a binary tree.

To find a inorder successor there are three situations

1. the node has a right child – the in-order successor will be in the right child, find the left most.

2. if the node does not have a right child – if the node is the left child of its parent, then the parent is the successor.

3. if the node does not have a right child – if the node is the right child of its parent, then the whole parent’s branch is done so the successor will be the parent’s successor, so we go up until we are left child, then the parent will be the next. (this is the difficult part)

### Like this:

Like Loading...

*Related*