This question is centered around the implementation of how transactions from a reorganized block return to the mempool.

In my understanding, once a block becomes organized out of the best chain all its transactions (that aren't in blocks of the best chain) need to return to the mempool.

Do we start from genesis block until we reach the last block of the active chain checking every transaction along the way, or is it there a more efficient algorithm that's based on some constraint/property that allows the algorithm to start from a more recent block?

Proto code for starting from the genesis block:

Blockchain blockchain = ...
function Dictionary<Key, Tx> deleteOrphanTx (Dictionary<Key, Tx> orphanTx) {
    foreach (Block currBlock : blockchain.getBlocks())
        foreach (Tx tx : currBlock.getTx())
            Key txKey = tx.getKey();
            if(orphanTx.contains(txKey)
                orphanTx.remove(txKey);
    return orphanTx;
}