Sachverhalt:
A.
Die F._ AG (Bauherrschaft) beabsichtigt, in Basel ein neues Bürohaus mit Wohnnutzung am Steinengraben 28-36 und daran angrenzend ein Wohnhaus an der Leonhardstrasse 27 zu errichten. Dafür sollen die Wohnhäuser Steinengraben 30-36 und Leonhardstrasse 27 abgebrochen und das Eckgebäude Steinengraben 28 umgebaut werden. Das Bau- und Gastgewerbeinspektorat des Kantons Basel-Stadt erteilte dafür mit Bauentscheid vom 16. März 2016 die Bewilligung und wies die dagegen gerichteten Einsprachen ab. Zu den Einsprechern gehörten A._, B._, C._, D._ und E._.
Die Baurekurskommission des Kantons Basel-Stadt hiess die Rechtsmittel der Einsprecher mit Entscheid vom 31. August 2016 teilweise gut, soweit sie darauf eintrat. Sie wies das Verfahren in Bezug auf die Ersatzpflanzung der zu fällenden Bäume an das Bau- und Gastgewerbeinspektorat zurück; im Übrigen wies sie die vorgebrachten Rügen zurück.
B.
Sowohl die Einsprecher als auch die Bauherrschaft zogen diesen Entscheid mit Rekursen an das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht weiter. Mit Urteil vom 25. September 2017 wies dieses die Rechtsmittel der Einsprecher ab und hiess jenes der Bauherrschaft gut. Im Ergebnis hob es den Entscheid der Rekurskommission vom 31. August 2016 auf und stellte den Bauentscheid vom 16. März 2016 wieder her.
C.
Gegen das Urteil des Appellationsgerichts führen A._, B._, C._, D._ und E._ mit Eingabe vom 30. November 2017 Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Sie beantragen, das angefochtene Urteil sei aufzuheben und die Bewilligung für das Bauvorhaben sei zu verweigern.
Die Bauherrschaft ersucht um Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Appellationsgericht schliesst auf Abweisung der Beschwerde. Die Baurekurskommission hat Verzicht auf Vernehmlassung erklärt. Das Bau- und Gastgewerbeinspektorat hat sich nicht vernehmen lassen.
In der Replik vom 27. März 2018 halten die Beschwerdeführer an den gestellten Rechtsbegehren fest. In der Folge haben sich die Verfahrensbeteiligten nicht mehr geäussert.
D.
Der Präsident der I. öffentlich-rechtlichen Abteilung hat der Beschwerde mit Verfügung vom 9. Januar 2018 die aufschiebende Wirkung zuerkannt.

Erwägungen:
1.
1.1. Angefochten ist ein kantonal letztinstanzlicher Endentscheid über eine baurechtliche Bewilligung (Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Art. 90 BGG). Dagegen steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen; ein Ausschlussgrund nach <ref-law> liegt nicht vor.
1.2. Umstritten ist die Beschwerdebefugnis der Beschwerdeführer. Diese haben am vorinstanzlichen Verfahren teilgenommen und sind durch die Abweisung ihrer Rechtsbegehren formell beschwert (<ref-law>). Nach den Feststellungen der Vorinstanz ist die Beschwerdeführerin 5 Mieterin und sind die Beschwerdeführer 1 bis 4 deren Untermieter in den streitbetroffenen Liegenschaften. Sie sind daher vom Gebäudeabbruch und Neubauprojekt besonders betroffen (<ref-law>). Die Beschwerdegegnerin bestreitet, dass sie ein schutzwürdiges Anfechtungsinteresse gemäss <ref-law> haben. Gemäss der Vorinstanz hat die Beschwerdegegnerin mit der Beschwerdeführerin 5 einen Vergleich bzw. Verträge abgeschlossen, wonach das Mietverhältnis bis zwei Monate nach Vorliegen einer rechtskräftigen Baubewilligung bestehen bleibt.
In der bundesgerichtlichen Rechtsprechung wird den Mietern ein schutzwürdiges Interesse an der Aufhebung eines Entscheids über den Abbruch oder den Umbau der von ihnen genutzten Liegenschaft zugebilligt (vgl. Urteile 1C_279/2016 vom 27. Februar 2017 E. 1; 1C_572/2011 vom 3. April 2012 E. 1.2; vgl. auch Urteil 1P.718/2003 vom 22. April 2004 E. 1 unter der Geltung des früheren Bundesgesetzes über die Organisation der Bundesrechtspflege vom 16. Dezember 1943). Diese Rechtsprechung bezieht sich auf Mieter, welche in der fraglichen Baute wohnen.
Die Beschwerdeführerin 5 hat den gemieteten Wohnraum als Zwischennutzung Untermietern wie den Beschwerdeführern 1 bis 4 überlassen. Auch wenn sie ihren Hauptwohnsitz an einen anderen Ort verlegt haben sollte, ändert dies aufgrund der besonderen vertraglichen Regelung mit der Beschwerdegegnerin nichts an ihrem gesicherten Nutzungsrecht. Die Beschwerdeführerin 5 hat auch nicht zu erkennen gegeben, dass sie eine Nutzung dieser Räumlichkeiten definitiv aufgegeben hätte. Die beschwerdeweise beantragte Aufhebung der Baubewilligung würde ihr einen praktischen Nutzen vermitteln. Somit ist bei ihr ein schutzwürdiges Interesse im Sinne von <ref-law> gegeben. Da auf die in ihrem Namen erhobene Beschwerde ohnehin einzutreten ist, kann offenbleiben, ob die Beschwerdeführer 1 bis 4 als Untermieter ebenfalls legitimiert sind. Die übrigen Sachurteilsvoraussetzungen geben keinen Anlass zu Bemerkungen.
2.
2.1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann geltend gemacht werden, der angefochtene Entscheid verletze Bundesrecht, Völkerrecht oder kantonale verfassungsmässige Rechte (Art. 95 lit. a, b und c BGG). Die Verletzung des übrigen kantonalen Rechts kann abgesehen von hier nicht relevanten Ausnahmen gemäss <ref-law> vor Bundesgericht nicht gerügt werden; zulässig ist jedoch der Vorwurf, die Anwendung dieses Rechts führe zu einer Verletzung von Bundesrecht, namentlich des verfassungsmässigen Willkürverbots (<ref-ruling> E. 2 S. 149 f.).
2.2. Die Beschwerdeführer beanstanden in verschiedener Hinsicht eine willkürliche Handhabung kantonalen Rechts. Nach der ständigen Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid aber nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 2.2 S. 72; <ref-ruling> E. 2.4 S. 5; je mit Hinweisen).
2.3. Eine Willkürrüge betrifft die Frage, ob das zur Diskussion stehende Projekt genügend Wohnraumersatz bietet. Gemäss § 7 Abs. 1 des kantonalen Gesetzes vom 5. Juni 2013 über die Wohnraumförderung (WRFG, SG 861.500) bedarf jeder Abbruch von Gebäuden, die vorwiegend Wohnzwecken dienen, einer Bewilligung. Die Abbruchbewilligung wird vorbehältlich der Einhaltung der nutzungsplanerischen Vorschriften zum Wohnanteil erteilt, wenn in der Folge mindestens gleich viel Wohnraum entsteht (§ 7 Abs. 3 lit. a WRFG) oder das zulässige Mass der baulichen Nutzung in einem städtebaulich sinnvollen Rahmen ausgeschöpft wird und der Anteil der Wohnnutzung gleich bleibt (§ 7 Abs. 3 lit. b WRFG). Im Streit liegt die Tragweite der Wendung "mindestens gleich viel Wohnraum entsteht" gemäss § 7 Abs. 3 lit. a WRFG. Die Anwendbarkeit dieser Bestimmung ist unbestritten. Das vorliegende Projekt erstreckt sich über mehrere Gebäude. Nach der Vorinstanz ist für das Verständnis von § 7 Abs. 3 lit. a WRFG eine ganzheitliche bzw. projektbezogene und nicht eine gebäudebezogene Sichtweise massgebend. Bei diesem Vergleich hat sie auch die Wohnflächen im umzubauenden Eckgebäude Steinengraben 28 eingerechnet. Die Beschwerdeführer wehren sich gegen den flächenmässigen Einbezug dieses Eckgebäudes. Dieses Gebäude werde nicht abgebrochen und es entstehe dort kein neuer Wohnraum. Die Auffassung im angefochtenen Urteil verstosse gegen den klaren Wortlaut von § 7 Abs. 3 lit. a WRFG und sei im Ergebnis unhaltbar.
2.4. Die Regelung in § 7 Abs. 1 und Abs. 3 lit. a WRFG hat den Regelfall eines Ersatzneubaus für ein einziges Gebäude vor Augen. Dies wird durch § 5 der Vollzugsverordnung (Verordnung vom 17. Juni 2014 über den Abbruch und die Zweckentfremdung von Wohnraum; VAZW; SG 730.400) verdeutlicht. Danach entsteht mindestens gleich viel Wohnraum, wenn die massgebliche Vergleichsfläche des Neubaus gleich oder grösser ist als diejenige des abzureissenden Gebäudes. Der Wortlaut von § 7 Abs. 3 lit. a WRFG schliesst nicht in klarer Weise die von den kantonalen Instanzen angestellte, gebäudeübergreifende Betrachtungsweise aus. Im Gegensatz zur Ansicht der Beschwerdeführer spricht der Wortlaut von § 7 Abs. 3 lit. a WRFG weder klar für die eine noch für die andere Lesart, weshalb die Bestimmung einer weitergehenden Auslegung bedarf. Neben dem Wortlaut der massgeblichen Bestimmung sind der Zweck der Regelung und der Sinnzusammenhang, in dem die Norm steht, zu berücksichtigen. Schliesslich dient auch die Entstehungsgeschichte als Hilfsmittel, um den Sinn der Norm zu erkennen (vgl. <ref-ruling> E. 3.3.1 S. 225 mit Hinweisen).
2.5. Die Vorinstanz erwägt unter Bezugnahme auf den unterinstanzlichen Baurekurskommissionsentscheid, dass nach den Gesetzesmaterialien die Schaffung von attraktivem Wohnraum gefördert und eine städtebauliche Veränderung nicht verunmöglicht werden solle. Sie betont damit stärker den gesetzlichen Zweck, dass Ersatzwohnraum geschaffen werde. Demgegenüber stellen die Beschwerdeführer den Erhalt des bestehenden Wohnraums an einem Standort ins Zentrum ihrer Argumentation und fordern eine restriktive Auslegung.
Nach der bundesgerichtlichen Rechtsprechung, die zur kantonalen Vorgängergesetzgebung (Gesetz über Abbruch und Zweckentfremdung von Wohnhäusern [GAZW] vom 20. November 1975) ergangen ist, ist letztere umso weniger streng auszulegen, je mehr die zu bekämpfende Wohnungsnot abklingt (vgl. <ref-ruling> E. 3c S. 41; Urteile vom 10. Februar 1982 E. 4, in: ZBl 84/1983 S. 375, und 1P.13/2000 vom 4. April 2000 E. 3a). Die Beschwerdeführer geben an, dass die Leerstandsquote in den letzten Jahren tief sei; dem widerspricht die Gegenseite nicht substanziiert. Ein solcher Umstand kann für eine restriktive Auslegung des Gesetzes sprechen. Im angefochtenen Urteil wird in allgemeiner Weise ausgeführt, dass das WRFG eine Lockerung im Vergleich zum GAZW darstelle. Ob die Vorinstanz allerdings im Rahmen des WRFG eine grundlegende Abkehr von der Gesetzesauslegung in Abhängigkeit von der Lage am Wohnungsmarkt vollziehen will, wird im angefochtenen Urteil nicht deutlich festgehalten. Darauf kommt es aber letztlich nicht entscheidend an. Die von den kantonalen Instanzen vertretene Auffassung hält bei der konkreten Konstellation unter dem Blickwinkel des Willkürverbots selbst einer strengen Gesetzesauslegung stand.
Das fragliche Projekt erstreckt sich über mehrere aneinander gebaute Häuser. Das umzubauende Eckgebäude gehört gemäss der Vorinstanz funktional und von der Fassadengestaltung her als integraler Bestandteil zu diesem Projekt. Diese Aspekte werden in der Beschwerdeschrift nicht substanziiert bestritten. Unter diesen Umständen ist es nicht unhaltbar, wenn der gesamte Gebäudekomplex als Einheit und damit als Vergleichsbasis für den Ersatzwohnraum genommen wird, selbst wenn ein Eckgebäude dabei lediglich umgebaut wird. Wie es sich verhält, wenn ein Bauprojekt den Um- und Neubau von nicht aneinander gebauten Häusern betrifft, braucht vorliegend nicht entschieden zu werden. Demzufolge geht der Willkürvorwurf betreffend Wohnraumersatz fehl.
3.
Ein zusätzlicher Rügekomplex richtet sich gegen die natur- bzw. baumschutzrechtliche Beurteilung des Projekts.
3.1. Ein Teil des bestehenden, hofseitigen Gartens der Liegenschaften wurde als schützenswertes Naturobjekt im Sinne von § 4 Abs. 2 lit. l des kantonalen Gesetzes vom 25. Januar 1995 über den Natur- und Landschaftsschutz (NLG; SG 789.100) eingestuft. Nach dieser Bestimmung können naturnahe Begrünung und unversiegelte Flächen, die das Stadt- und Ortsbild und dessen ökologische Qualität mitbestimmen, ein schützenswertes Objekt bilden. Die Vorinstanz teilt die Ansicht der Unterinstanzen, dass dem Garten aufgrund seiner Funktion als Trittsteinbiotop Schutzqualität zukomme. Weiter geht sie mit den Unterinstanzen einig, dass fünf Einzelbäume auf dem Areal Objekte im Sinne des kantonalen Baumschutzgesetzes vom 16. Oktober 1980 (BSchG; SG 789.700) bilden.
3.2. Die Zerstörung dieses Biotops und die Fällung der angesprochenen Bäume hat die Vorinstanz mit dem überwiegenden Interesse der Beschwerdegegnerin an der Erstellung des Neubauprojekts samt Tiefgarage gerechtfertigt. Die nach § 6 BSchG erforderliche Baumfällbewilligung hat sie geschützt. Weiter hat die Vorinstanz die im Bauentscheid festgehaltenen Wiederherstellungs- bzw. Ersatzmassnahmen als ausreichend erachtet. Durch den Bauentscheid wird die Beschwerdegegnerin in diesem Sinne verpflichtet, die Umgebung mit naturnahen Elementen als vielfältigen Lebensraum zu gestalten. Es seien überwiegend standortheimische und landschaftstypische Pflanzen zu verwenden. Als Ersatz für die gefällten Bäume wird die Anpflanzung von drei mittel- bis grosskronigen Bäumen auf nicht unterkellertem Areal und von zwei mittelkronigen Ersatzbäumen auf unterkellertem Areal angeordnet. Die Dicke der durchwurzelbaren Erdschicht muss im Bereich von Baumpflanzungen mindestens 100 cm betragen. Der Beschwerdegegnerin wird weiter die Pflicht zu einer im Einzelnen konkretisierten Dachbegrünung sowie zu näher umschriebenen Massnahmen für den Vogelschutz bzw. zur Wahrung von Nistmöglichkeiten von Tieren an Gebäuden oder Bäumen auferlegt.
Der Bauentscheid enthält im Übrigen im Sinne einer Nebenbestimmung gemäss § 51 Abs. 2 der kantonalen Bau- und Planungsverordnung vom 19. Dezember 2000 (BPV; GS 730.110) den Vorbehalt, dass die Beschwerdegegnerin vor Baubeginn einen detaillierten Umgebungs- und Bepflanzungsplan sowie einen Baumbestandesplan zur Genehmigung einzureichen hat. Auch diese Nebenbestimmung hat die Vorinstanz für rechtmässig erachtet.
Die Beschwerdeführer bestreiten, dass die im Bauentscheid angeordneten Massnahmen, insbesondere die Ersatzpflanzung der fünf Bäume, durchführbar sind bzw. zur Kompensation des Verlusts ausreichen. Zudem verletzt die Nebenbestimmung über die vorbehaltenen Pläne nach ihrer Meinung den Grundsatz der Einheit des Bauentscheids.
3.3. Das Koordinationsgebot (Art. 25a RPG [SR 700]) verlangt, dass die für die Errichtung einer Baute erforderlichen Verfügungen materiell und soweit möglich formell koordiniert ergehen (Abs. 1-3). Der Grundsatz der Einheit des Bauentscheids lässt die teilweise Bewilligung einer Baute oder Überbauung nur zu, wenn der bewilligte Teil unabhängig vom nicht bewilligten Teil beurteilt werden kann. Auch bei einer Aufteilung eines Bauvorhabens in verschiedene Teilschritte und Bewilligungsverfahren sind die Gesamtauswirkungen des Vorhabens zu prüfen (<ref-ruling> E. 26b S. 346 f.). Demnach kann die Aufteilung einer Baubewilligung in mehrere Zwischen- oder Teilverfügungen gegen das Gebot der materiellen Koordination gemäss Art. 25a RPG und der umfassenden Interessenabwägung verstossen, wenn sich einzelne Aspekte oder Anlagenteile nicht sinnvoll isoliert beurteilen lassen, sondern eine Gesamtschau verlangen (Urteil 1C_150/2009 vom 8. September 2009 E. 2.2 mit Hinweisen). Nach allgemeinen Grundsätzen dürfen jedoch im Baubewilligungsverfahren die Farbgebung der Fassaden oder andere Einzelheiten der Aussenraumgestaltung einer nachträglichen Definition und Entscheidung vorbehalten werden, wenn diese nicht mit anderen Bewilligungen koordiniert werden müssen (vgl. Urteil 1C_327/2016 vom 22. März 2017 E. 9.3 unter Hinweis auf ZAUGG/LUDWIG, Baugesetz des Kantons Bern vom 9. Juni 1985, 4. Aufl. 2013 Band I., N. 17 zu Art. 38-39 BauG/BE).
Lässt sich eine Beeinträchtigung schutzwürdiger Lebensräume unter Abwägung aller Interessen nicht vermeiden, so hat der Verursacher für besondere Massnahmen zu deren bestmöglichem Schutz, für Wiederherstellung oder ansonsten für angemessenen Ersatz gemäss Art. 18 Abs. 1 ter NHG [SR 451] i.V.m. Art. 14 Abs. 6 und 7 NHV [SR 451.1] zu sorgen (vgl. Urteil 1C_164/2012 vom 30. Januar 2013 E. 6.1). Wiederherstellungs- und Ersatzmassnahmen nach Art. 18 Abs. 1 ter NHG sind integrale Bestandteile des Bauvorhabens und unterliegen der Koordinationspflicht gemäss Art. 25a RPG. Allerdings ist es auch bei derartigen Vorhaben zuweilen unumgänglich, dass der Grundsatzentscheid über die Zulässigkeit eines Vorhabens vor dem Entscheid über weitere Bewilligungen getroffen werden muss. Eine solche Aufteilung kann zulässig sein, sofern die erforderliche materielle und (soweit möglich) formelle Koordination der Entscheide nicht vereitelt wird (vgl. Urteil 1C_156/2012 vom 12. Oktober 2012 E. 6.2.2 in: URP 2013 S. 357).
Im vorliegenden Fall kann offenbleiben, ob es sich bei dem geschützten Gartenbereich um ein Biotop von lokaler Bedeutung im Sinne von <ref-law> handelt. Auch wenn dieser Gartenbereich nur nach kantonalem Recht geschützt sein sollte, unterliegt die danach vorgeschriebene Wiederherstellungs- und Ersatzpflicht (vgl. § 9 NLG) in analoger Weise dem Koordinationsgebot gemäss Art. 25a RPG. Bezüglich des kantonal geregelten Baumschutzes ist ebenfalls eine Koordinationspflicht zu bejahen, soweit - wie vorliegend - Ersatzanpflanzungen beim Neubau auf dem Areal verlangt werden.
3.4. Im Hinblick auf den Ersatzgarten ergibt sich aus dem Bauentscheid der Mindestanteil an Grünflächen auf dem Areal und es werden qualitative Vorgaben für die Neubepflanzung festgelegt. Im angefochtenen Urteil wird erläutert, dass keine Anhaltspunkte für das Vorhandensein gefährdeter oder sonst für die städtische Fauna und Flora wichtiger Arten vorgebracht worden seien. Grossflächige Nutzungseinschränkungen hat die Vorinstanz für den Ersatzgarten abgelehnt. Im Rahmen des vorbehaltenen Nachverfahrens sind insbesondere die genauen Standorte der Grünflächen und deren Ausgestaltung sowie die verwendeten Pflanzenarten zu klären.
Vor Bundesgericht wenden die Beschwerdeführer im Wesentlichen ein, die Vorgaben im Bauentscheid zum Ersatzgarten seien nicht konkret formuliert und würden eine Beurteilung der Angemessenheit der Naturschutzmassnahmen nicht ermöglichen. Im angefochtenen Urteil wird auf den Vorwurf, dass angeblich im Bauentscheid konkrete Wiederherstellungs- bzw. Ersatzmassnahmen bezüglich des Gartens fehlen, eingegangen. Diese Erwägungen nehmen Bezug auf die gegenteilige, fachliche Beurteilung durch die Stadtgärtnerei. Letztere hat sich namentlich in der Stellungnahme vom 20. Juni 2016 zu ihrer Vegetationsaufnahme im bestehenden Gartenbereich und zur Bewertung der Qualität des Ersatzes bei den angeordneten Massnahmen geäussert.
Damit der ersatzweise zu schaffende Garten als Trittsteinbiotop die gebotene Vernetzungsfunktion langfristig ausüben kann, reicht es im konkreten Fall aus, dass die Vorgaben im Bauentscheid im Wesentlichen dauerhaft eine naturnahe Bepflanzung und eine Ausgestaltung als vielfältigen Lebensraum verlangen. Mit der Festlegung der angesprochenen Parameter im Bauentscheid als Wiederherstellungs- bzw. Ersatzmassnahmen für den Garten durfte es vorliegend sein Bewenden haben.
3.5. Weiter hat sich die Vorinstanz eingehend mit den Rahmenbedingungen des Bauentscheids zum Ersatz der fünf Bäume befasst. Nach ihren Feststellungen verfügt die Erdschicht über der Tiefgarage gemäss dem bewilligten Bauprojekt über die im Bauentscheid verlangte Mächtigkeit. Eine solche Überdeckung sei ausreichend, damit sich mittelkronige Bäume uneingeschränkt entwickeln können. Ausserdem sind in den bewilligten Bauplänen beim Aussenraum Aussparungen aus der Tiefgarage ausgeschieden, die nach Ansicht der Vorinstanz insgesamt die Anpflanzung von drei mittelkronigen Bäumen ermöglichen. Es sei zwar zu erwarten, dass diese Bäume ihre Wurzeln über die Aussparung hinaus in den überdeckten Bereich über der Tiefgarage ausschlagen werden. Grössere Aussparungen seien aber nicht nötig. Auch über der Tiefgarage sei die Erdschicht - wie dargelegt - ausreichend dick für mittelkronige Bäume. Aufgrund dessen erachtet die Vorinstanz die angeordnete Ersatzpflanzung von zwei Bäumen auf unterkellertem und drei Bäumen auf nicht unterkellertem Bereich als grundsätzlich erfüllbar. Darüber hinaus geht die Vorinstanz davon aus, dass eine allfällige Abdichtung bzw. Sanierung der bewilligten Tiefgarage in den nächsten 70 Jahren unterirdisch erfolgen könne, so dass die Ersatzbäume nicht wieder gefällt werden müssten. Bei den Überlegungen zu den Ersatzbäumen hat sich die Vorinstanz wiederum auf Stellungnahmen der Stadtgärtnerei gestützt; ebenso hat sie die abweichende Beurteilung durch einen Baumschutzexperten, dem die unterinstanzliche Baurekurskommission gefolgt war, gewürdigt. In der Beschwerdeschrift werden keine konkreten Anhaltspunkte aufgezeigt, dass die geschilderten Feststellungen und Prognosen der Vorinstanz offensichtlich unzutreffend sein sollen. Bei dieser Sachlage durfte sie den Ersatz der fünf Bäume aufgrund der Vorgaben im Bauentscheid als sichergestellt betrachten. Die davon abweichenden Vorbringen der Beschwerdeführer überzeugen nicht. Die spezifische Baumart und der genaue Standort spielen bei den fünf Bäumen keine derart erhebliche Rolle, dass sie bereits im Bauentscheid festzulegen waren.
3.6. Ebenso wenig ist es zu beanstanden, dass die im Bauentscheid vorbehaltenen Umgebungs-, Bepflanzungs- und Baumbestandespläne erst vor Baubeginn zur Genehmigung eingereicht werden müssen. Die Pflicht zur Nachreichung dieser Pläne hat die Vorinstanz zutreffend als Suspensivbedingung qualifiziert; den Beschwerdeführern kann nicht beigepflichtet werden, wenn sie diese als blosse Auflagen ansehen (vgl. zur Unterscheidung Urteil 1C_398/2016 vom 2. Februar 2017 E. 2.6 in: ZBl 118/2017 S. 614). An dieser Schlussfolgerung ändert es nichts, dass der Beginn der Abbrucharbeiten nicht an die vorbehaltene Genehmigung dieser Pläne gekoppelt ist. Wesentlich ist die Umsetzbarkeit der fraglichen Massnahmen beim Neubau. Soweit es im Übrigen - unabhängig von den genannten Plänen - um die oben bei E. 3.2 erwähnte Wahrung von Nistmöglichkeiten geht, ergibt sich aus der entsprechenden Nebenbestimmung, dass die Abklärungen zur Gefahr allfälliger Beeinträchtigungen im Nachgang zum Bauentscheid an den bestehenden Bäumen und Gebäuden - und somit bereits vor der Fällung bzw. dem Abbruch - durchgeführt werden müssen.
3.7. Wie aus den vorstehenden Erwägungen (oben E. 3.4 bis 3.6) hervorgeht, verletzt der Vorbehalt im Bauentscheid zur Nachreichung der genannten Detailpläne betreffend Natur- und Baumschutz das Koordinationsgebot von Art. 25a RPG nicht. Entgegen der Meinung der Beschwerdeführer wurden die vorgeschriebenen Wiederherstellungs- und Ersatzmassnahmen für den Gartenbereich und die fünf Einzelbäume in genügender Weise im Rahmen des Bauentscheids bestimmt. Auch in der Sache verstösst es weder gegen Art. 18 Abs. 1 ter NHG, soweit diese Vorschrift anwendbar ist, noch in willkürlicher Weise gegen das einschlägige kantonale Recht, dass die Vorinstanz die fraglichen Anordnungen als ausreichende Schutzmassnahmen eingestuft hat. Das angefochtene Urteil ist in diesem Punkt nicht mangelhaft begründet, sondern genügt den Anforderungen von <ref-law> (vgl. dazu <ref-ruling> E. 2.1 S. 145 mit Hinweisen).
4.
Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang sind die Gerichtskosten den unterliegenden Beschwerdeführern aufzuerlegen (Art. 66 Abs. 1 und 5 BGG). Diese haben der Beschwerdegegnerin unter solidarischer Haftbarkeit eine angemessene Parteientschädigung für das bundesgerichtliche Verfahren auszurichten (Art. 68 Abs. 1, 2 und 4 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 4'000.-- werden den Beschwerdeführern auferlegt.
3.
Die Beschwerdeführer haben der Beschwerdegegnerin eine Parteientschädigung von insgesamt Fr. 4'000.-- zu bezahlen.
4.
Dieses Urteil wird den Parteien, dem Bau- und Gastgewerbeinspektorat Basel-Stadt, der Baurekurskommission des Kantons Basel-Stadt, und dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht, Dreiergericht, schriftlich mitgeteilt.
Lausanne, 18. September 2018
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Chaix
Der Gerichtsschreiber: Kessler Coendet