In Order Successor in Binary Search Tree

shreyasva picture shreyasva · Mar 29, 2011 · Viewed 43.3k times · Source

Given a node in a BST, how does one find the next higher key?

Answer

Lasse V. Karlsen picture Lasse V. Karlsen · Mar 29, 2011

The general way depends on whether you have a parent link in your nodes or not.

If you store the parent link

Then you pick:

  1. The leftmost child of the right child, if your current node has a right child. If the right child has no left child, the right child is your inorder successor.
  2. Navigate up the parent ancestor nodes, and when you find a parent whose left child is the node you're currently at, the parent is the inorder successor of your original node.

If you have right child, do this approach (case 1 above):

inorder-when-right-child

If you don't have a right child, do this approach (case 2 above):

inorder-when-no-right-child

If you don't store the parent link

Then you need to run a complete scan of the tree, keeping track of the nodes, usually with a stack, so that you have the information necessary to basically do the same as the first method that relied on the parent link.