Inorder Successor in BST
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
Binary Search
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root == null || p == null) return null;
else if(p.right != null){
// find successor directly
p = p.right;
while(p.left != null)
p = p.left;
return p;
}else{
//binary search to find p and prev node
TreeNode curr = root, prev = null;
while(curr != p){
if(curr.val > p.val){
prev = curr;
curr = curr.left;
}else{
curr = curr.right;
}
}
return prev;
}
}
O(n), flat BST to list.
private List<TreeNode> flatList = new ArrayList<>();
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root == null || p == null)
return null;
inorderTraversal(root);
for(int i = 0; i < flatList.size(); i++){
if(flatList.get(i) == p && i + 1 < flatList.size())
return flatList.get(i + 1);
}
return null;
}
private void inorderTraversal(TreeNode root){
if(root == null)
return;
inorderTraversal(root.left);
flatList.add(root);
inorderTraversal(root.right);
}