diff --git a/clang/include/clang/AST/NestedNameSpecifier.h b/clang/include/clang/AST/NestedNameSpecifier.h
--- a/clang/include/clang/AST/NestedNameSpecifier.h
+++ b/clang/include/clang/AST/NestedNameSpecifier.h
@@ -17,6 +17,7 @@
 #include "clang/AST/DependenceFlags.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT//DenseMapInfo.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/Support/Compiler.h"
@@ -527,4 +528,35 @@
 
 } // namespace clang
 
+namespace llvm {
+
+// Define DenseMapInfo so that DeclarationNames can be used as keys
+// in DenseMap and DenseSets.
+template <> struct DenseMapInfo<clang::NestedNameSpecifierLoc> {
+  using FirstInfo = DenseMapInfo<clang::NestedNameSpecifier *>;
+  using SecondInfo = DenseMapInfo<void *>;
+
+  static inline clang::NestedNameSpecifierLoc getEmptyKey() {
+    return clang::NestedNameSpecifierLoc(FirstInfo::getEmptyKey(),
+                                         SecondInfo::getEmptyKey());
+  }
+
+  static inline clang::NestedNameSpecifierLoc getTombstoneKey() {
+    return clang::NestedNameSpecifierLoc(FirstInfo::getTombstoneKey(),
+                                         SecondInfo::getTombstoneKey());
+  }
+
+  static unsigned getHashValue(const clang::NestedNameSpecifierLoc &PairVal) {
+    return detail::combineHashValue(
+        FirstInfo::getHashValue(PairVal.getNestedNameSpecifier()),
+        SecondInfo::getHashValue(PairVal.getOpaqueData()));
+  }
+
+  static bool isEqual(const clang::NestedNameSpecifierLoc &LHS,
+                      const clang::NestedNameSpecifierLoc &RHS) {
+    return LHS == RHS;
+  }
+};
+} // namespace llvm
+
 #endif // LLVM_CLANG_AST_NESTEDNAMESPECIFIER_H
diff --git a/clang/lib/Tooling/Syntax/BuildTree.cpp b/clang/lib/Tooling/Syntax/BuildTree.cpp
--- a/clang/lib/Tooling/Syntax/BuildTree.cpp
+++ b/clang/lib/Tooling/Syntax/BuildTree.cpp
@@ -241,10 +241,24 @@
     assert(Added && "mapping added twice");
   }
 
+  void add(NestedNameSpecifierLoc From, syntax::Tree *To) {
+    assert(To != nullptr);
+    assert(From.hasQualifier());
+
+    bool Added = NNSNodes.insert({From, To}).second;
+    (void)Added;
+    assert(Added && "mapping added twice");
+  }
+
   syntax::Tree *find(ASTPtr P) const { return Nodes.lookup(P); }
 
+  syntax::Tree *find(NestedNameSpecifierLoc P) const {
+    return NNSNodes.lookup(P);
+  }
+
 private:
   llvm::DenseMap<ASTPtr, syntax::Tree *> Nodes;
+  llvm::DenseMap<NestedNameSpecifierLoc, syntax::Tree *> NNSNodes;
 };
 } // namespace
 
@@ -281,16 +295,20 @@
     if (From)
       Mapping.add(From, New);
   }
+
   void foldNode(ArrayRef<syntax::Token> Range, syntax::Tree *New, TypeLoc L) {
     // FIXME: add mapping for TypeLocs
     foldNode(Range, New, nullptr);
   }
 
-  void foldNode(ArrayRef<syntax::Token> Range, syntax::Tree *New,
-                NestedNameSpecifierLoc L) {
-    // FIXME: add mapping for NestedNameSpecifierLoc
-    foldNode(Range, New, nullptr);
+  void foldNode(llvm::ArrayRef<syntax::Token> Range, syntax::Tree *New,
+                NestedNameSpecifierLoc From) {
+    assert(New);
+    Pending.foldChildren(Arena, Range, New);
+    if (From)
+      Mapping.add(From, New);
   }
+
   /// Notifies that we should not consume trailing semicolon when computing
   /// token range of \p D.
   void noticeDeclWithoutSemicolon(Decl *D);
@@ -312,6 +330,8 @@
   void markChild(syntax::Node *N, NodeRole R);
   /// Set role for the syntax node matching \p N.
   void markChild(ASTPtr N, NodeRole R);
+  /// Set role for the syntax node matching \p N.
+  void markChild(NestedNameSpecifierLoc N, NodeRole R);
 
   /// Finish building the tree and consume the root node.
   syntax::TranslationUnit *finalize() && {
@@ -798,31 +818,31 @@
     return SR;
   }
 
-  syntax::NestedNameSpecifier *
-  BuildNestedNameSpecifier(const NestedNameSpecifierLoc &QualifierLoc) {
+  // To build syntax tree nodes for NestedNameSpecifierLoc we override Traverse
+  // instead of WalkUpFrom because we want to traverse the children ourselves
+  // and build a list instead of a nested tree of name specifier prefixes.
+  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc QualifierLoc) {
     if (!QualifierLoc)
-      return nullptr;
+      return true;
     for (auto it = QualifierLoc; it; it = it.getPrefix()) {
-      assert(it.hasQualifier());
       auto *NS = BuildNameSpecifier(*it.getNestedNameSpecifier());
       assert(NS);
       if (!isa<syntax::GlobalNameSpecifier>(NS))
         Builder.foldNode(Builder.getRange(getLocalSourceRange(it)).drop_back(),
-                         NS, it);
+                         NS, nullptr);
       Builder.markChild(NS, syntax::NodeRole::NestedNameSpecifier_specifier);
       Builder.markChildToken(it.getEndLoc(),
                              syntax::NodeRole::NestedNameSpecifier_delimiter);
     }
-    auto *NNS = new (allocator()) syntax::NestedNameSpecifier;
-    Builder.foldNode(Builder.getRange(QualifierLoc.getSourceRange()), NNS,
+    Builder.foldNode(Builder.getRange(QualifierLoc.getSourceRange()),
+                     new (allocator()) syntax::NestedNameSpecifier,
                      QualifierLoc);
-    return NNS;
+    return true;
   }
 
   bool WalkUpFromDeclRefExpr(DeclRefExpr *S) {
-    auto *Qualifier = BuildNestedNameSpecifier(S->getQualifierLoc());
-    if (Qualifier)
-      Builder.markChild(Qualifier, syntax::NodeRole::IdExpression_qualifier);
+    if (auto QualifierLoc = S->getQualifierLoc())
+      Builder.markChild(QualifierLoc, syntax::NodeRole::IdExpression_qualifier);
 
     auto TemplateKeywordLoc = S->getTemplateKeywordLoc();
     if (TemplateKeywordLoc.isValid())
@@ -843,9 +863,8 @@
 
   // Same logic as DeclRefExpr.
   bool WalkUpFromDependentScopeDeclRefExpr(DependentScopeDeclRefExpr *S) {
-    auto *Qualifier = BuildNestedNameSpecifier(S->getQualifierLoc());
-    if (Qualifier)
-      Builder.markChild(Qualifier, syntax::NodeRole::IdExpression_qualifier);
+    if (auto QualifierLoc = S->getQualifierLoc())
+      Builder.markChild(QualifierLoc, syntax::NodeRole::IdExpression_qualifier);
 
     auto TemplateKeywordLoc = S->getTemplateKeywordLoc();
     if (TemplateKeywordLoc.isValid())
@@ -1399,6 +1418,11 @@
   assert(SN != nullptr);
   setRole(SN, R);
 }
+void syntax::TreeBuilder::markChild(NestedNameSpecifierLoc NNSLoc, NodeRole R) {
+  auto *SN = Mapping.find(NNSLoc);
+  assert(SN != nullptr);
+  setRole(SN, R);
+}
 
 void syntax::TreeBuilder::markStmtChild(Stmt *Child, NodeRole Role) {
   if (!Child)
diff --git a/clang/unittests/Tooling/Syntax/TreeTest.cpp b/clang/unittests/Tooling/Syntax/TreeTest.cpp
--- a/clang/unittests/Tooling/Syntax/TreeTest.cpp
+++ b/clang/unittests/Tooling/Syntax/TreeTest.cpp
@@ -2973,7 +2973,8 @@
 `-UsingNamespaceDirective
   |-using
   |-namespace
-  |-::
+  |-NestedNameSpecifier
+  | `-::
   |-ns
   `-;
 )txt"));
@@ -3002,8 +3003,10 @@
 | `-}
 `-UsingDeclaration
   |-using
-  |-ns
-  |-::
+  |-NestedNameSpecifier
+  | |-IdentifierNameSpecifier
+  | | `-ns
+  | `-::
   |-a
   `-;
 )txt"));
@@ -3207,11 +3210,13 @@
   |->
   `-SimpleDeclaration
     |-struct
-    |-X
-    |-<
-    |-T
-    |->
-    |-::
+    |-NestedNameSpecifier
+    | |-SimpleTemplateNameSpecifier
+    | | |-X
+    | | |-<
+    | | |-T
+    | | `->
+    | `-::
     |-Y
     |-{
     |-}
@@ -3245,15 +3250,19 @@
     |-{
     |-UsingDeclaration
     | |-using
-    | |-T
-    | |-::
+    | |-NestedNameSpecifier
+    | | |-IdentifierNameSpecifier
+    | | | `-T
+    | | `-::
     | |-foo
     | `-;
     |-UsingDeclaration
     | |-using
     | |-typename
-    | |-T
-    | |-::
+    | |-NestedNameSpecifier
+    | | |-IdentifierNameSpecifier
+    | | | `-T
+    | | `-::
     | |-bar
     | `-;
     |-}