diff --git a/clang/include/clang/Tooling/Syntax/Tree.h b/clang/include/clang/Tooling/Syntax/Tree.h
--- a/clang/include/clang/Tooling/Syntax/Tree.h
+++ b/clang/include/clang/Tooling/Syntax/Tree.h
@@ -106,6 +106,8 @@
 
   const Node *getNextSibling() const { return NextSibling; }
   Node *getNextSibling() { return NextSibling; }
+  const Node *getPreviousSibling() const { return PreviousSibling; }
+  Node *getPreviousSibling() { return PreviousSibling; }
 
   /// Dumps the structure of a subtree. For debugging and testing purposes.
   std::string dump(const SourceManager &SM) const;
@@ -132,6 +134,7 @@
 
   Tree *Parent;
   Node *NextSibling;
+  Node *PreviousSibling;
   unsigned Kind : 16;
   unsigned Role : 8;
   unsigned Original : 1;
@@ -158,6 +161,8 @@
 
   Node *getFirstChild() { return FirstChild; }
   const Node *getFirstChild() const { return FirstChild; }
+  Node *getLastChild() { return LastChild; }
+  const Node *getLastChild() const { return LastChild; }
 
   Leaf *findFirstLeaf();
   const Leaf *findFirstLeaf() const {
@@ -193,6 +198,7 @@
   friend class MutationsImpl;
 
   Node *FirstChild = nullptr;
+  Node *LastChild = nullptr;
 };
 
 /// A list of Elements separated or terminated by a fixed token.
diff --git a/clang/lib/Tooling/Syntax/Mutations.cpp b/clang/lib/Tooling/Syntax/Mutations.cpp
--- a/clang/lib/Tooling/Syntax/Mutations.cpp
+++ b/clang/lib/Tooling/Syntax/Mutations.cpp
@@ -23,19 +23,6 @@
 
 using namespace clang;
 
-static syntax::Node *findPrevious(syntax::Node *N) {
-  assert(N);
-  assert(N->getParent());
-  if (N->getParent()->getFirstChild() == N)
-    return nullptr;
-  for (syntax::Node *C = N->getParent()->getFirstChild(); C != nullptr;
-       C = C->getNextSibling()) {
-    if (C->getNextSibling() == N)
-      return C;
-  }
-  llvm_unreachable("could not find a child node");
-}
-
 // This class has access to the internals of tree nodes. Its sole purpose is to
 // define helpers that allow implementing the high-level mutation operations.
 class syntax::MutationsImpl {
@@ -46,6 +33,7 @@
     assert(Anchor->Parent != nullptr);
     assert(New->Parent == nullptr);
     assert(New->NextSibling == nullptr);
+    assert(New->PreviousSibling == nullptr);
     assert(New->isDetached());
     assert(Role != NodeRole::Detached);
 
@@ -63,11 +51,13 @@
     assert(Old->canModify());
     assert(New->Parent == nullptr);
     assert(New->NextSibling == nullptr);
+    assert(New->PreviousSibling == nullptr);
     assert(New->isDetached());
 
     New->Role = Old->Role;
     auto *P = Old->getParent();
-    P->replaceChildRangeLowLevel(findPrevious(Old), Old->getNextSibling(), New);
+    P->replaceChildRangeLowLevel(Old->getPreviousSibling(),
+                                 Old->getNextSibling(), New);
 
     P->assertInvariants();
   }
@@ -79,7 +69,7 @@
     assert(N->canModify());
 
     auto *P = N->getParent();
-    P->replaceChildRangeLowLevel(findPrevious(N), N->getNextSibling(),
+    P->replaceChildRangeLowLevel(N->getPreviousSibling(), N->getNextSibling(),
                                  /*New=*/nullptr);
 
     P->assertInvariants();
diff --git a/clang/lib/Tooling/Syntax/Tree.cpp b/clang/lib/Tooling/Syntax/Tree.cpp
--- a/clang/lib/Tooling/Syntax/Tree.cpp
+++ b/clang/lib/Tooling/Syntax/Tree.cpp
@@ -57,8 +57,9 @@
 }
 
 syntax::Node::Node(NodeKind Kind)
-    : Parent(nullptr), NextSibling(nullptr), Kind(static_cast<unsigned>(Kind)),
-      Role(0), Original(false), CanModify(false) {
+    : Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),
+      Kind(static_cast<unsigned>(Kind)), Role(0), Original(false),
+      CanModify(false) {
   this->setRole(NodeRole::Detached);
 }
 
@@ -85,10 +86,16 @@
 void syntax::Tree::prependChildLowLevel(Node *Child) {
   assert(Child->Parent == nullptr);
   assert(Child->NextSibling == nullptr);
+  assert(Child->PreviousSibling == nullptr);
   assert(Child->getRole() != NodeRole::Detached);
 
   Child->Parent = this;
-  Child->NextSibling = this->FirstChild;
+  if (this->FirstChild) {
+    Child->NextSibling = this->FirstChild;
+    this->FirstChild->PreviousSibling = Child;
+  } else
+    this->LastChild = Child;
+
   this->FirstChild = Child;
 }
 
@@ -100,6 +107,7 @@
   assert(canModify() && "Cannot modify `this`.");
 
   Node *&Begin = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
+  Node *&Last = End ? End->PreviousSibling : LastChild;
 
 #ifndef NDEBUG
   for (auto *N = New; N; N = N->NextSibling) {
@@ -135,6 +143,7 @@
     N->setRole(NodeRole::Detached);
     N->Parent = nullptr;
     N->NextSibling = nullptr;
+    N->PreviousSibling = nullptr;
     if (N->Original)
       traverse(N, [](Node *C) { C->Original = false; });
 
@@ -143,16 +152,19 @@
 
   if (!New) {
     Begin = End;
+    Last = BeforeBegin;
     return;
   }
   // Attach new nodes.
   Begin = New;
-  auto *Last = New;
+  New->PreviousSibling = BeforeBegin;
+  auto *LastInNew = New;
   for (auto *N = New; N != nullptr; N = N->NextSibling) {
-    Last = N;
+    LastInNew = N;
     N->Parent = this;
   }
-  Last->NextSibling = End;
+  LastInNew->NextSibling = End;
+  Last = LastInNew;
 }
 
 namespace {
@@ -243,11 +255,20 @@
   const auto *T = dyn_cast<Tree>(this);
   if (!T)
     return;
+
+  const auto *Last = T->getFirstChild();
+  for (; Last && Last->getNextSibling(); Last = Last->getNextSibling())
+    ;
+  assert(Last == T->getLastChild() &&
+         "Last child is reachable by advancing from the first child.");
+
   for (const auto *C = T->getFirstChild(); C; C = C->getNextSibling()) {
     if (T->isOriginal())
       assert(C->isOriginal());
     assert(!C->isDetached());
     assert(C->getParent() == T);
+    const auto *Next = C->getNextSibling();
+    assert(!Next || C == Next->getPreviousSibling());
   }
 
   const auto *L = dyn_cast<List>(T);
@@ -282,14 +303,13 @@
 }
 
 syntax::Leaf *syntax::Tree::findLastLeaf() {
-  syntax::Leaf *Last = nullptr;
-  for (auto *C = getFirstChild(); C; C = C->getNextSibling()) {
+  for (auto *C = getLastChild(); C; C = C->getPreviousSibling()) {
     if (auto *L = dyn_cast<syntax::Leaf>(C))
-      Last = L;
-    else if (auto *L = cast<syntax::Tree>(C)->findLastLeaf())
-      Last = L;
+      return L;
+    if (auto *L = cast<syntax::Tree>(C)->findLastLeaf())
+      return L;
   }
-  return Last;
+  return nullptr;
 }
 
 syntax::Node *syntax::Tree::findChild(NodeRole R) {