Consider implement these two helper functions: <ol type="i"><li><code>getPredecessor(N)</code>, which returns the next smaller node to N.</li> <li><code>getSuccessor(N)</code>, which returns the next larger node to N.</li> </ol>

Try to assume that each node has a parent pointer, it makes the problem much easier.

Without parent pointer we just need to keep track of the path from the root to the current node using a stack.

You would need two stacks to track the path in finding predecessor and successor node separately.