life is fun

# Inorder Successor in Binary Search Tree

http://www.geeksforgeeks.org/archives/9999

Parent pointer is needed in this algorithm.
The Algorithm is divided into two cases on the basis of right subtree of the input node being empty or not.

Input: node, root // node is the node whose Inorder successor is needed.
output: succ // succ is Inorder successor of node.

1) If right subtree of node is not NULL, then succ lies in right subtree. Do following.
Go to right subtree and return the node with minimum key value in right subtree.
2) If right sbtree of node is NULL, then start from root and us search like technique. Do following.
Travel down the tree, if a node’s data is greater than root’s data then go right side, otherwise go to left side.

 `struct` `node * inOrderSuccessor(``struct` `node *root, ``struct` `node *n)` `{` `    ``// step 1 of the above algorithm` `    ``if``( n->right != NULL )` `        ``return` `minValue(n->right);`   `    ``struct` `node *succ = NULL;`   `    ``// Start from root and search for successor down the tree` `    ``while` `(root != NULL)` `    ``{` `        ``if` `(n->data < root->data)` `        ``{` `            ``succ = root;` `            ``root = root->left;` `        ``}` `        ``else` `if` `(n->data > root->data)` `            ``root = root->right;` `        ``else` `           ``break``;` `    ``}`   `    ``return` `succ;` `}`

Time Complexity: O(h) where h is height of tree.

Standard