diff --git a/TestMediaApp/assets/media_items/advanced.json b/TestMediaApp/assets/media_items/advanced.json
index a6befa3..45a18ef 100644
--- a/TestMediaApp/assets/media_items/advanced.json
+++ b/TestMediaApp/assets/media_items/advanced.json
@@ -39,7 +39,7 @@
     },
     {
       "FLAGS": "browsable",
-      "PLAYABLE_HINT": "GRID",
+      "BROWSABLE_HINT": "GRID_CATEGORY",
       "METADATA": {
         "MEDIA_ID": "advanced art nodes",
         "DISPLAY_TITLE": "Album Art"
diff --git a/TestMediaApp/assets/media_items/album_art/art_nodes.json b/TestMediaApp/assets/media_items/album_art/art_nodes.json
index 974268b..692809f 100644
--- a/TestMediaApp/assets/media_items/album_art/art_nodes.json
+++ b/TestMediaApp/assets/media_items/album_art/art_nodes.json
@@ -1,6 +1,6 @@
 {
   "FLAGS": "browsable",
-  "BROWSABLE_HINT": "LIST",
+  "BROWSABLE_HINT": "GRID_CATEGORY",
 
   "METADATA": {
     "MEDIA_ID": "album_art/art_nodes",
diff --git a/TestMediaApp/assets/media_items/mixed.json b/TestMediaApp/assets/media_items/mixed.json
index 7e04e85..34da9c9 100644
--- a/TestMediaApp/assets/media_items/mixed.json
+++ b/TestMediaApp/assets/media_items/mixed.json
@@ -1,7 +1,7 @@
 {
   "FLAGS": "browsable",
   "PLAYABLE_HINT": "GRID",
-  "BROWSABLE_HINT": "LIST",
+  "BROWSABLE_HINT": "LIST_CATEGORY",
 
   "METADATA": {
     "MEDIA_ID": "mixed",
diff --git a/TestMediaApp/assets/media_items/only_nodes.json b/TestMediaApp/assets/media_items/only_nodes.json
index a020abd..26f998e 100644
--- a/TestMediaApp/assets/media_items/only_nodes.json
+++ b/TestMediaApp/assets/media_items/only_nodes.json
@@ -32,7 +32,7 @@
     {
       "FLAGS": "browsable",
       "PLAYABLE_HINT": "GRID",
-      "BROWSABLE_HINT": "LIST",
+      "BROWSABLE_HINT": "LIST_CATEGORY",
       "METADATA": {
         "MEDIA_ID": "only_nodes rabbit hole",
         "DISPLAY_TITLE": "Rabbit hole 2"
diff --git a/TestMediaApp/src/com/android/car/media/testmediaapp/MediaKeys.java b/TestMediaApp/src/com/android/car/media/testmediaapp/MediaKeys.java
index 9c58483..9fba1a8 100644
--- a/TestMediaApp/src/com/android/car/media/testmediaapp/MediaKeys.java
+++ b/TestMediaApp/src/com/android/car/media/testmediaapp/MediaKeys.java
@@ -65,4 +65,18 @@
      * hints the corresponding items should be presented as grids.
      */
     static final int CONTENT_STYLE_GRID_ITEM_HINT_VALUE = 2;
+
+    /**
+     * Value for {@link #CONTENT_STYLE_BROWSABLE_HINT} that hints the corresponding items should be
+     * presented as a "category" list, where media items are browsable and represented by a
+     * meaningful icon.
+     */
+    public static final int CONTENT_STYLE_CATEGORY_LIST_ITEM_HINT_VALUE = 3;
+
+    /**
+     * Value for {@link #CONTENT_STYLE_BROWSABLE_HINT} that hints the corresponding items should be
+     * presented as a "category" grid, where media items are browsable and represented by a
+     * meaningful icon.
+     */
+    public static final int CONTENT_STYLE_CATEGORY_GRID_ITEM_HINT_VALUE = 4;
 }
diff --git a/TestMediaApp/src/com/android/car/media/testmediaapp/TmaBrowser.java b/TestMediaApp/src/com/android/car/media/testmediaapp/TmaBrowser.java
index 079ab3b..7a62137 100644
--- a/TestMediaApp/src/com/android/car/media/testmediaapp/TmaBrowser.java
+++ b/TestMediaApp/src/com/android/car/media/testmediaapp/TmaBrowser.java
@@ -39,6 +39,8 @@
 
 import java.util.ArrayList;
 import java.util.List;
+import java.util.regex.Matcher;
+import java.util.regex.Pattern;
 
 
 /**
@@ -52,6 +54,7 @@
 public class TmaBrowser extends MediaBrowserServiceCompat {
     private static final String TAG = "TmaBrowser";
 
+    private static final int MAX_SEARCH_DEPTH = 4;
     private static final String MEDIA_SESSION_TAG = "TEST_MEDIA_SESSION";
     private static final String ROOT_ID = "_ROOT_ID_";
     private static final String SEARCH_SUPPORTED = "android.media.browse.SEARCH_SUPPORTED";
@@ -68,7 +71,6 @@
     private TmaPlayer mPlayer;
 
     private BrowserRoot mRoot;
-    private String mLastLoadedNodeId;
 
     @Override
     public void onCreate() {
@@ -163,7 +165,6 @@
 
     @Override
     public void onLoadChildren(@NonNull String parentId, @NonNull Result<List<MediaItem>> result) {
-        mLastLoadedNodeId = parentId;
         getMediaItemsWithDelay(parentId, result, null);
 
         if (QUEUE_ONLY.equals(mPrefs.mRootNodeType.getValue()) && ROOT_ID.equals(parentId)) {
@@ -176,8 +177,9 @@
     }
 
     @Override
-    public void onSearch(final String query, final Bundle extras, Result<List<MediaItem>> result) {
-        getMediaItemsWithDelay(mLastLoadedNodeId, result, query);
+    public void onSearch(@NonNull String query, Bundle extras,
+            @NonNull Result<List<MediaItem>> result) {
+        getMediaItemsWithDelay(ROOT_ID, result, query);
     }
 
     private void getMediaItemsWithDelay(@NonNull String parentId,
@@ -196,14 +198,15 @@
 
             if (node == null) {
                 result.sendResult(null);
+            } else if (filter != null) {
+                List<MediaItem> hits = new ArrayList<>(50);
+                Pattern pat = Pattern.compile(Pattern.quote(filter), Pattern.CASE_INSENSITIVE);
+                addSearchResults(node, pat.matcher(""), hits, MAX_SEARCH_DEPTH);
+                result.sendResult(hits);
             } else {
                 List<MediaItem> items = new ArrayList<>(node.mChildren.size());
                 for (TmaMediaItem child : node.mChildren) {
-                    MediaItem item = child.toMediaItem();
-                    CharSequence title = item.getDescription().getTitle();
-                    if (filter == null || (title != null && title.toString().contains(filter))) {
-                        items.add(item);
-                    }
+                    items.add(child.toMediaItem());
                 }
                 result.sendResult(items);
             }
@@ -215,4 +218,26 @@
             mHandler.postDelayed(task, delay.mReplyDelayMs);
         }
     }
+
+    private void addSearchResults(@Nullable TmaMediaItem node, Matcher matcher,
+            List<MediaItem> hits, int currentDepth) {
+        if (node == null || currentDepth <= 0) {
+            return;
+        }
+
+        for (TmaMediaItem child : node.mChildren) {
+            MediaItem item = child.toMediaItem();
+            CharSequence title = item.getDescription().getTitle();
+            if (title != null) {
+                matcher.reset(title);
+                if (matcher.find()) {
+                    hits.add(item);
+                }
+            }
+
+            // Ask the library to load the grand children
+            child = mLibrary.getMediaItemById(child.getMediaId());
+            addSearchResults(child, matcher, hits, currentDepth - 1);
+        }
+    }
 }
diff --git a/TestMediaApp/src/com/android/car/media/testmediaapp/TmaMediaItem.java b/TestMediaApp/src/com/android/car/media/testmediaapp/TmaMediaItem.java
index f79e273..af1b2e3 100644
--- a/TestMediaApp/src/com/android/car/media/testmediaapp/TmaMediaItem.java
+++ b/TestMediaApp/src/com/android/car/media/testmediaapp/TmaMediaItem.java
@@ -42,7 +42,9 @@
     public enum ContentStyle {
         NONE (0),
         LIST (MediaKeys.CONTENT_STYLE_LIST_ITEM_HINT_VALUE),
-        GRID (MediaKeys.CONTENT_STYLE_GRID_ITEM_HINT_VALUE);
+        GRID (MediaKeys.CONTENT_STYLE_GRID_ITEM_HINT_VALUE),
+        LIST_CATEGORY(MediaKeys.CONTENT_STYLE_CATEGORY_LIST_ITEM_HINT_VALUE),
+        GRID_CATEGORY(MediaKeys.CONTENT_STYLE_CATEGORY_GRID_ITEM_HINT_VALUE);
         final int mBundleValue;
         ContentStyle(int value) {
             mBundleValue = value;