diff --git a/core/api/src/main/java/org/onosproject/store/primitives/DefaultConsistentTreeMap.java b/core/api/src/main/java/org/onosproject/store/primitives/DefaultConsistentTreeMap.java
index 782a1ec..a38da9e 100644
--- a/core/api/src/main/java/org/onosproject/store/primitives/DefaultConsistentTreeMap.java
+++ b/core/api/src/main/java/org/onosproject/store/primitives/DefaultConsistentTreeMap.java
@@ -45,7 +45,6 @@
 public class DefaultConsistentTreeMap<V>
         extends Synchronous<AsyncConsistentTreeMap<V>>
         implements ConsistentTreeMap<V> {
-    private static final int MAX_DELAY_BETWEEN_RETRY_MILLIS = 50;
     private final AsyncConsistentTreeMap<V> treeMap;
     private final long operationTimeoutMillis;
     private Map<String, V> javaMap;
diff --git a/core/api/src/main/java/org/onosproject/store/primitives/DistributedPrimitiveCreator.java b/core/api/src/main/java/org/onosproject/store/primitives/DistributedPrimitiveCreator.java
index 5080b82..a8827a7 100644
--- a/core/api/src/main/java/org/onosproject/store/primitives/DistributedPrimitiveCreator.java
+++ b/core/api/src/main/java/org/onosproject/store/primitives/DistributedPrimitiveCreator.java
@@ -20,6 +20,7 @@
 import org.onosproject.store.service.AsyncAtomicCounter;
 import org.onosproject.store.service.AsyncAtomicValue;
 import org.onosproject.store.service.AsyncConsistentMap;
+import org.onosproject.store.service.AsyncConsistentTreeMap;
 import org.onosproject.store.service.AsyncDistributedSet;
 import org.onosproject.store.service.AsyncLeaderElector;
 import org.onosproject.store.service.WorkQueue;
@@ -42,6 +43,16 @@
     <K, V> AsyncConsistentMap<K, V> newAsyncConsistentMap(String name, Serializer serializer);
 
     /**
+     * Creates a new {@code AsyncConsistentTreeMap}.
+     *
+     * @param name tree name
+     * @param serializer serializer to use for serializing/deserializing map entries
+     * @param <V> value type
+     * @return distributedTreeMap
+     */
+    <V> AsyncConsistentTreeMap<V> newAsyncConsistentTreeMap(String name, Serializer serializer);
+
+    /**
      * Creates a new {@code AsyncAtomicCounter}.
      *
      * @param name counter name
diff --git a/core/api/src/main/java/org/onosproject/store/service/ConsistentTreeMapBuilder.java b/core/api/src/main/java/org/onosproject/store/service/ConsistentTreeMapBuilder.java
new file mode 100644
index 0000000..bb343da
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/ConsistentTreeMapBuilder.java
@@ -0,0 +1,61 @@
+/*
+ * Copyright 2016-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.store.service;
+
+import org.onosproject.store.primitives.DistributedPrimitiveBuilder;
+
+/**
+ * Builder for {@link ConsistentTreeMap}.
+ */
+public abstract class ConsistentTreeMapBuilder<V>
+        extends DistributedPrimitiveBuilder<ConsistentTreeMapBuilder<V>, ConsistentTreeMap<V>> {
+
+    private boolean purgeOnUninstall = false;
+
+    public ConsistentTreeMapBuilder() {
+        super(DistributedPrimitive.Type.CONSISTENT_TREEMAP);
+    }
+
+    /**
+     * Clears map contents when the owning application is uninstalled.
+     *
+     * @return this builder
+     */
+    public ConsistentTreeMapBuilder<V> withPurgeOnUninstall() {
+        purgeOnUninstall = true;
+        return this;
+    }
+
+    /**
+     * Return if map entries need to be cleared when owning application is uninstalled.
+     *
+     * @return true if items are to be cleared on uninstall
+     */
+    public boolean purgeOnUninstall() {
+        return purgeOnUninstall;
+    }
+
+    /**
+     * Builds the distributed tree map based on the configuration options supplied
+     * to this builder.
+     *
+     * @return new distributed tree map
+     * @throw java.lang.RuntimeException if a mandatory parameter is missing
+     */
+    public abstract AsyncConsistentTreeMap<V> buildTreeMap();
+
+}
diff --git a/core/api/src/main/java/org/onosproject/store/service/DistributedPrimitive.java b/core/api/src/main/java/org/onosproject/store/service/DistributedPrimitive.java
index b19a04b..8a2c7ba 100644
--- a/core/api/src/main/java/org/onosproject/store/service/DistributedPrimitive.java
+++ b/core/api/src/main/java/org/onosproject/store/service/DistributedPrimitive.java
@@ -52,6 +52,11 @@
         SET,
 
         /**
+         * Tree map.
+         */
+        CONSISTENT_TREEMAP,
+
+        /**
          * atomic counter.
          */
         COUNTER,
diff --git a/core/api/src/main/java/org/onosproject/store/service/StorageService.java b/core/api/src/main/java/org/onosproject/store/service/StorageService.java
index e646e38..4edb438 100644
--- a/core/api/src/main/java/org/onosproject/store/service/StorageService.java
+++ b/core/api/src/main/java/org/onosproject/store/service/StorageService.java
@@ -44,6 +44,14 @@
     <K, V> ConsistentMapBuilder<K, V> consistentMapBuilder();
 
     /**
+     * Creates a new {@code AsyncConsistentTreeMapBuilder}.
+     *
+     * @param <V> value type
+     * @return builder for a async consistent tree map
+     */
+    <V> ConsistentTreeMapBuilder<V> consistentTreeMapBuilder();
+
+    /**
      * Creates a new DistributedSetBuilder.
      *
      * @param <E> set element type