Find the next node(i.e. in-order successor) of a node in a binary tree

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)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s