Finding successor and predecessor in bst in O(1)

If in each node you also store the reference to the parent, then you can see how you would be able to find the next node, given a node:

getNext(node):
    if node.right is not null:
        node = node.right
        while node.left is not null:
            node = node.left
        return node
    while node.parent is not null:
        if node.parent.left == node:  # node is a left child
            return node.parent
        node = node.parent  # node was a right child
    # no more nodes...
    return null

As you see, there are loops involved, so this takes a varying time. In the worst case, the node that follows a leaf may be the root, and the node following the root may be a deep leaf. So one call may involve up to h reassignments to node, following that many edges in the tree (h is the height of the tree).

But if you consider a complete traversal over all nodes, starting at the left-most leaf, you see that each edge is traversed exactly 2 times: first with either left or right, and second with parent. Except for the edges on the path from the root to the left-most leaf: those are only visited once, with parent. But for simplicity, let's just say they are also visited twice (we over-estimate the work slightly).

That means that for the n calls to getNext (where the previous result is fed into the next call and the last call returns null), you would visit 2(n-1) edges, meaning that on average one call traverses 2(n-1)/n edges, which is always (slightly) less than 2.

Therefore this represents an amortised O(1) time complexity.

Of course, the algorithm for getPrevious would be similar and have the same time complexity considerations.

The algorithms for insert and delete operations (including rotations in self-balancing trees) can be easily extended to also update the parent reference in each involved node without increasing the time complexity.