find inorder successor in BST without using any extra space.

Question

I am looking a way to find out inorder successor of a node in BST withut using extra space.

Answer 1

If you can access the root of a node, then it's just a matter of moving pointers around, so no extra space. See this lecture.

Answer 2

If the given node has a right child - go to it, and then follow iteratively the left children until you reach a node N with no left children. Return N.

Otherwise, follow the parents until you first find a parent where the node is a left child. Return this parent.

Node InOrderSuccessor(Node node) {
    if (node.right() != null) {
        node = node.right()
        while (node.left() != null) 
            node = node.left()
        return node
    } else {
        parent = node.getParent();
        while (parent != null && parent.right() == node) {
            node = parent
            parent = node.getParent()
        }
        return parent
    }
}