Find the inorder predecessor and successor of a given key in a binary search tree.

To find the inorder predecessor we should follow the rules
10
/ \
5 12
/\ /
3 7 11
1. If the node has a left chlid then we find the right most child in the left subtree. In the above example node 10’s predecessor is 7
2. If the node does not have a left child, if it is the right child of its parent, then its parent will be the predecessor.
3. If the node does not have a left child and it is the left child of its parent. Then we need to follow up the tree until we find a node that is a right child of its parent. In the above example, node 11’s predecessor is 10.

The in-order successor is basically the same.

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