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
@@ -224,6 +224,34 @@
   return SourceRange(Start, End);
 }
 
+namespace llvm {
+template <> struct DenseMapInfo<clang::NestedNameSpecifierLoc> {
+  using FirstInfo = DenseMapInfo<clang::NestedNameSpecifier *>;
+  using SecondInfo = DenseMapInfo<void *>;
+
+  static inline NestedNameSpecifierLoc getEmptyKey() {
+    return NestedNameSpecifierLoc(FirstInfo::getEmptyKey(),
+                                  SecondInfo::getEmptyKey());
+  }
+
+  static inline NestedNameSpecifierLoc getTombstoneKey() {
+    return 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 NestedNameSpecifierLoc &LHS,
+                      const NestedNameSpecifierLoc &RHS) {
+    return LHS == RHS;
+  }
+};
+} // namespace llvm
+
 namespace {
 /// All AST hierarchy roots that can be represented as pointers.
 using ASTPtr = llvm::PointerUnion<Stmt *, Decl *>;
@@ -243,8 +271,22 @@
 
   syntax::Tree *find(ASTPtr P) const { return Nodes.lookup(P); }
 
+  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(NestedNameSpecifierLoc P) const {
+    return NNSNodes.lookup(P);
+  }
+
 private:
   llvm::DenseMap<ASTPtr, syntax::Tree *> Nodes;
+  llvm::DenseMap<NestedNameSpecifierLoc, syntax::Tree *> NNSNodes;
 };
 } // namespace
 
@@ -289,9 +331,11 @@
   }
 
   void foldNode(llvm::ArrayRef<syntax::Token> Range, syntax::Tree *New,
-                NestedNameSpecifierLoc L) {
-    // FIXME: add mapping for NestedNameSpecifierLoc
-    foldNode(Range, New, nullptr);
+                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.
@@ -315,6 +359,9 @@
   /// 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() && {
     auto Tokens = Arena.tokenBuffer().expandedTokens();
@@ -842,10 +889,9 @@
     return NS;
   }
 
-  syntax::NestedNameSpecifier *
-  BuildNestedNameSpecifier(const NestedNameSpecifierLoc &QualifierLoc) {
+  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc QualifierLoc) {
     if (!QualifierLoc)
-      return nullptr;
+      return true;
     for (auto it = QualifierLoc; it; it = it.getPrefix()) {
       auto *NS = BuildNameSpecifier(it);
       assert(NS);
@@ -853,17 +899,16 @@
       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())
       Builder.markChildToken(TemplateKeywordLoc,
@@ -883,10 +928,9 @@
 
   // FIXME: Same logic as DeclRefExpr. How to DRY
   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())
       Builder.markChildToken(TemplateKeywordLoc,
@@ -1440,6 +1484,12 @@
   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)
     return;
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
@@ -1232,9 +1232,7 @@
     | | | | | `-DecltypeSpecifier
     | | | | |   |-decltype
     | | | | |   |-(
-    | | | | |   |-IdExpression
-    | | | | |   | `-UnqualifiedId
-    | | | | |   |   `-s
+    | | | | |   |-s
     | | | | |   `-)
     | | | | `-::
     | | | `-UnqualifiedId
@@ -2980,7 +2978,8 @@
 `-UsingNamespaceDirective
   |-using
   |-namespace
-  |-::
+  |-NestedNameSpecifier
+  | `-::
   |-ns
   `-;
 )txt"));
@@ -3009,8 +3008,10 @@
 | `-}
 `-UsingDeclaration
   |-using
-  |-ns
-  |-::
+  |-NestedNameSpecifier
+  | |-NameSpecifier
+  | | `-ns
+  | `-::
   |-a
   `-;
 )txt"));
@@ -3214,11 +3215,14 @@
   |->
   `-SimpleDeclaration
     |-struct
-    |-X
-    |-<
-    |-T
-    |->
-    |-::
+    |-NestedNameSpecifier
+    | |-NameSpecifier
+    | | `-SimpleTemplateSpecifier
+    | |   |-X
+    | |   |-<
+    | |   |-T
+    | |   `->
+    | `-::
     |-Y
     |-{
     |-}
@@ -3252,15 +3256,19 @@
     |-{
     |-UsingDeclaration
     | |-using
-    | |-T
-    | |-::
+    | |-NestedNameSpecifier
+    | | |-NameSpecifier
+    | | | `-T
+    | | `-::
     | |-foo
     | `-;
     |-UsingDeclaration
     | |-using
     | |-typename
-    | |-T
-    | |-::
+    | |-NestedNameSpecifier
+    | | |-NameSpecifier
+    | | | `-T
+    | | `-::
     | |-bar
     | `-;
     |-}