# Next Node in BST

In Binary Tree, Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inoorder traversal.

In Binary Search Tree, Inorder Successor of an input node can also be defined as the node with the smallest key greater than the key of input node. So, it is sometimes important to find next node in sorted order.

## Solution

If p has a right subtree, then get its successor from there. Otherwise do a regular search from root to p but remember the node of the last left-turn and return that. Same solution as everyone, I guess, just written a bit shorter.

## Complexity

Runtime O(h), where h is the height of the tree.

## Code

Iterative Successor

``````public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if (p.right != null) {
p = p.right;
while (p.left != null)
p = p.left;
return p;
}
TreeNode candidate = null;
while (root != p)
root = (p.val > root.val) ? root.right : (candidate = root).left;
return candidate;
}
``````

Recursive Successor

``````public TreeNode successor(TreeNode root, TreeNode p) {
if (root == null)
return null;

if (root.val <= p.val) {
return successor(root.right, p);
} else {
TreeNode left = successor(root.left, p);
return (left != null) ? left : root;
}
}
``````

Recursive predecessor

``````public TreeNode predecessor(TreeNode root, TreeNode p) {
if (root == null)
return null;

if (root.val >= p.val) {
return predecessor(root.left, p);
} else {
TreeNode right = predecessor(root.right, p);
return (right != null) ? right : root;
}
}
``````