Find the next node (in-oder traversal) of a given node in a binary search tree

Problem

Write an algorithm to find the next node (i.e., in-oder successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.

Solution

This problem can be solved by thinking the two patterns. First pattern is in case the given node has right node, and second pattern is in case the given node dose not have right node.

the node has right node

In this case, the next node can be calculated by the following steps.

1. traverse right node once.
2. traverse left node until the left node is null
3. when the loop is broken, the node is next node.

This traversal is to bottom.

the node dose not have right node

In this case, the next node can be calculated by the following steps.

1. traverse the parent node until the left node of the parent node dose not coincide the current node.
2. when the above loop is broken, the node is next node.

This traversal is to up.

Source Code