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

Inorder Successor in BST

The Essence:

The in-order successor of a node in a binary search tree node is basically the smallest node that has a larger value than the node's. There are few properties that can be derived from the structure of BST:

• If it's a left node and it has no right nodes, its successor would be its parent.
• If a parent has a right node, it is this if the right node does not have any left nodes, which would have been smaller than this right node.
• If the right child of parent has left children, then the smallest next values are sought there.

Details:

The procedure described here can be implemented both recursively and iteratively. The implementation can be found here: https://github.com/spiralgo/algorithms/pull/326