Yes. Please do.
For inspiration, you can google image search one of the most amazing places I've ever been to: Petra. It is very complete from residences to commercial and community facilities, as well as rudimentary utilities, including a stormwater drainage system. Other answers have given you examples, so I will build off of theirs by adding my experience of Petra.
It took us three full days of exploring, and while the Bank was made famous by Indiana Jones, El Dier was incredibly complex inside.
Height - Your mountain is the limit, you can build as high as the environment allows, or as deep as the material allows. Petra's highest residences were G+6 (ground +6 stories), but because it was in the sandstone mountains, the entire site, with abundant 'roads' and staircases rose about 300m from the base of the city to the higher residences - maybe more (I can't find this information online).
Lumber - You can limit lumber to the functional spaces, as you like: doors, etc. In this example, lumber survived the years and served to close portals such as windows and doorways.
Color - Petra is called the Rose City by some, and it is exactly the color you seem to be describing.
Ornate-ness - Very. As you will see from your google-image search, the precedent that I'm discussing had very ornate carving, which held up against the elements because half the site is below ground level, and there is limited rainwater. I can't imagine how much more intricacy has been worn away by the wind.
Durability - The only threat to your city is from the elements. Please protect it, since I'm now kind of falling in love with your city, from rainwater, and keep your river from washing it away. Petra has been known to exist for over 2,000 years in a relatively dry climate.
If you want more elaborate utilities, sandstone is very pliable, as shown in the examples provided by other answers.
Another beautiful example was the beautiful horizontal and vertical troglodytes of Tunisia. Horizontal 'cave dwellings' are carved into the sides of (in Tunisia) sandstone, while vertical are carved down. They were occupied until about the 1960s (no source), but we helped a guy from a nearby University establish an eco-hotel out of one of them. They are between 1 and 10 stories vertically ("the mountain's the limit"), and being rock, they moderate temperatures in your desert.
In fact, one of the very real troglodytes is in a town called Tataouine, whose name has been transferred to a popular movie, which filmed there several times, and took the name.