Binary tree interview: implement follow operation

just keep the maximum element for the tree and always return it for nodes v < maximum.

You can get O(1) if you store pointers to the "next node" (using your O(log(n) algorithm), given you are allowed to do that.

How about:

int tree[N];

size_t follow(size_t v) {
    // First try the right child
    size_t w = v * 2 + 1;
    if(w >= N) {
        // Otherwise right sibling
        w = v + 1;
        if(w >= N) {
            // Finally right parent
            w = (v - 1) / 2 + 1;
        }
    }
    return w;
}

Where tree is a complete binary tree in array form and v/w are represented as zero-based indices.

One idea is to literally just have a next pointer on each node.

You can update these pointers in O(height) after an insert or remove (O(height) is O(log n) for a self-balancing BST), which is as long as an insert or remove takes, so it doesn't add to the time complexity.

Alternatively, you can also have a previous pointer in addition to the next pointer. If you do this, you can update these pointers in O(1).

Obviously, in either case, if you have a node, you also have its next pointer, and you can simply get this value in O(1).

Pseudo-code

For only a next pointer, after the insert, you'd do:

if inserted as a right child:
   newNode.next = parent.next
   parent.next = newNode
else // left child
   predecessor(newNode)

For both next and previous pointers:

if inserted as a right child:
   parent.next.previous = newNode
   newNode.next = parent.next
   parent.next = newNode
else // left child
   parent.previous.next = newNode
   newNode.previous = parent.previous
   parent.previous = newNode

(some null checks are also required).