LC: 510. Inorder Successor in BST II - spiralgo/algorithms GitHub Wiki

The Essence:

(is stands for Inorder Successor)

For this problem, one needs to be familiar with traversal of binary trees and trees in general.

In-order traversal is proceeds in the sequence: left-root-right

Once could see from this that:

If a node has a right node, then the is should be the leftmost node at that side of tree.
Else, if a node has a parent node and its left node is the node, then the is is the node's parent.
Else, if a node has a parent node and its right node is the given node, then the is is the parent's parent if its parent is its corresponding left node, if its however the right node, then we must recursively climb up the tree, until we find a node that is its parent's left node.
If all these do not work, then the result is null, as there is no is.

Details:

All the procedures described here can be implemented recursively, something common with binary tree problems. Finding the left most node of the right child and closest left-parent can be supported by iteration too.