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.

Advertisements