diff --git a/services/surfaceflinger/tests/unittests/Android.bp b/services/surfaceflinger/tests/unittests/Android.bp
index 26c0d8e..914c5f9 100644
--- a/services/surfaceflinger/tests/unittests/Android.bp
+++ b/services/surfaceflinger/tests/unittests/Android.bp
@@ -92,6 +92,7 @@
         "LayerHistoryTest.cpp",
         "LayerInfoTest.cpp",
         "LayerMetadataTest.cpp",
+        "LayerHierarchyTest.cpp",
         "LayerLifecycleManagerTest.cpp",
         "LayerTest.cpp",
         "LayerTestUtils.cpp",
diff --git a/services/surfaceflinger/tests/unittests/LayerHierarchyTest.cpp b/services/surfaceflinger/tests/unittests/LayerHierarchyTest.cpp
new file mode 100644
index 0000000..8560902
--- /dev/null
+++ b/services/surfaceflinger/tests/unittests/LayerHierarchyTest.cpp
@@ -0,0 +1,728 @@
+/*
+ * Copyright 2022 The Android Open Source Project
+ *
+ * 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.
+ */
+
+#include <gmock/gmock.h>
+#include <gtest/gtest.h>
+
+#include "FrontEnd/LayerHandle.h"
+#include "FrontEnd/LayerHierarchy.h"
+#include "FrontEnd/LayerLifecycleManager.h"
+#include "Layer.h"
+#include "gui/SurfaceComposerClient.h"
+
+#define UPDATE_AND_VERIFY(HIERARCHY)  \
+    ({                                \
+        SCOPED_TRACE("");             \
+        updateAndVerify((HIERARCHY)); \
+    })
+
+namespace android::surfaceflinger::frontend {
+
+namespace {
+LayerCreationArgs createArgs(uint32_t id, bool canBeRoot, wp<IBinder> parent, wp<IBinder> mirror) {
+    LayerCreationArgs args(nullptr, nullptr, "testlayer", 0, {}, std::make_optional(id));
+    args.addToRoot = canBeRoot;
+    args.parentHandle = parent;
+    args.mirrorLayerHandle = mirror;
+    return args;
+}
+} // namespace
+
+// To run test:
+/**
+ mp :libsurfaceflinger_unittest && adb sync; adb shell \
+    /data/nativetest/libsurfaceflinger_unittest/libsurfaceflinger_unittest \
+    --gtest_filter="LayerHierarchyTest.*" --gtest_repeat=100 \
+    --gtest_shuffle \
+    --gtest_brief=1
+*/
+
+class LayerHierarchyTest : public testing::Test {
+protected:
+    LayerHierarchyTest() {
+        // tree with 3 levels of children
+        // ROOT
+        // ├── 1
+        // │   ├── 11
+        // │   │   └── 111
+        // │   ├── 12
+        // │   │   ├── 121
+        // │   │   └── 122
+        // │   │       └── 1221
+        // │   └── 13
+        // └── 2
+
+        createRootLayer(1);
+        createRootLayer(2);
+        createLayer(11, 1);
+        createLayer(12, 1);
+        createLayer(13, 1);
+        createLayer(111, 11);
+        createLayer(121, 12);
+        createLayer(122, 12);
+        createLayer(1221, 122);
+        mLifecycleManager.commitChanges();
+    }
+    std::vector<uint32_t> getTraversalPath(const LayerHierarchy& hierarchy) const {
+        std::vector<uint32_t> layerIds;
+        hierarchy.traverse([&layerIds = layerIds](const LayerHierarchy& hierarchy,
+                                                  const LayerHierarchy::TraversalPath&) -> bool {
+            layerIds.emplace_back(hierarchy.getLayer()->id);
+            return true;
+        });
+        return layerIds;
+    }
+
+    std::vector<uint32_t> getTraversalPathInZOrder(const LayerHierarchy& hierarchy) const {
+        std::vector<uint32_t> layerIds;
+        hierarchy.traverseInZOrder(
+                [&layerIds = layerIds](const LayerHierarchy& hierarchy,
+                                       const LayerHierarchy::TraversalPath&) -> bool {
+                    layerIds.emplace_back(hierarchy.getLayer()->id);
+                    return true;
+                });
+        return layerIds;
+    }
+
+    void createRootLayer(uint32_t id) {
+        sp<LayerHandle> handle = sp<LayerHandle>::make(id);
+        mHandles[id] = handle;
+        std::vector<std::unique_ptr<RequestedLayerState>> layers;
+        layers.emplace_back(std::make_unique<RequestedLayerState>(
+                createArgs(/*id=*/id, /*canBeRoot=*/true, /*parent=*/nullptr, /*mirror=*/nullptr)));
+        mLifecycleManager.addLayers(std::move(layers));
+    }
+
+    void createLayer(uint32_t id, uint32_t parentId) {
+        sp<LayerHandle> handle = sp<LayerHandle>::make(id);
+        mHandles[id] = handle;
+        std::vector<std::unique_ptr<RequestedLayerState>> layers;
+        layers.emplace_back(std::make_unique<RequestedLayerState>(
+                createArgs(/*id=*/id, /*canBeRoot=*/false, /*parent=*/mHandles[parentId],
+                           /*mirror=*/nullptr)));
+        mLifecycleManager.addLayers(std::move(layers));
+    }
+
+    void reparentLayer(uint32_t id, uint32_t newParentId) {
+        std::vector<TransactionState> transactions;
+        transactions.emplace_back();
+        transactions.back().states.push_back({});
+
+        if (newParentId == UNASSIGNED_LAYER_ID) {
+            transactions.back().states.front().state.parentSurfaceControlForChild = nullptr;
+        } else {
+            auto parentHandle = mHandles[newParentId];
+            transactions.back().states.front().state.parentSurfaceControlForChild =
+                    sp<SurfaceControl>::make(SurfaceComposerClient::getDefault(), parentHandle,
+                                             static_cast<int32_t>(newParentId), "Test");
+        }
+        transactions.back().states.front().state.what = layer_state_t::eReparent;
+        transactions.back().states.front().state.surface = mHandles[id];
+        mLifecycleManager.applyTransactions(transactions);
+    }
+
+    void reparentRelativeLayer(uint32_t id, uint32_t relativeParentId) {
+        std::vector<TransactionState> transactions;
+        transactions.emplace_back();
+        transactions.back().states.push_back({});
+
+        if (relativeParentId == UNASSIGNED_LAYER_ID) {
+            transactions.back().states.front().state.what = layer_state_t::eLayerChanged;
+        } else {
+            auto parentHandle = mHandles[relativeParentId];
+            transactions.back().states.front().state.relativeLayerSurfaceControl =
+                    sp<SurfaceControl>::make(SurfaceComposerClient::getDefault(), parentHandle,
+                                             static_cast<int32_t>(relativeParentId), "test");
+            transactions.back().states.front().state.what = layer_state_t::eRelativeLayerChanged;
+        }
+        transactions.back().states.front().state.surface = mHandles[id];
+        mLifecycleManager.applyTransactions(transactions);
+    }
+
+    void mirrorLayer(uint32_t id, uint32_t parent, uint32_t layerToMirror) {
+        auto parentHandle = (parent == UNASSIGNED_LAYER_ID) ? nullptr : mHandles[parent];
+        auto mirrorHandle =
+                (layerToMirror == UNASSIGNED_LAYER_ID) ? nullptr : mHandles[layerToMirror];
+
+        sp<LayerHandle> handle = sp<LayerHandle>::make(id);
+        mHandles[id] = handle;
+        std::vector<std::unique_ptr<RequestedLayerState>> layers;
+        layers.emplace_back(std::make_unique<RequestedLayerState>(
+                createArgs(/*id=*/id, /*canBeRoot=*/false, /*parent=*/parentHandle,
+                           /*mirror=*/mHandles[layerToMirror])));
+        mLifecycleManager.addLayers(std::move(layers));
+    }
+
+    void updateBackgroundColor(uint32_t id, half alpha) {
+        std::vector<TransactionState> transactions;
+        transactions.emplace_back();
+        transactions.back().states.push_back({});
+        transactions.back().states.front().state.what = layer_state_t::eBackgroundColorChanged;
+        transactions.back().states.front().state.bgColorAlpha = alpha;
+        transactions.back().states.front().state.surface = mHandles[id];
+        mLifecycleManager.applyTransactions(transactions);
+    }
+
+    void destroyLayerHandle(uint32_t id) { mLifecycleManager.onHandlesDestroyed({id}); }
+
+    void updateAndVerify(LayerHierarchyBuilder& hierarchyBuilder) {
+        if (mLifecycleManager.getGlobalChanges().test(RequestedLayerState::Changes::Hierarchy)) {
+            hierarchyBuilder.update(mLifecycleManager.getLayers(),
+                                    mLifecycleManager.getDestroyedLayers());
+        }
+        mLifecycleManager.commitChanges();
+
+        // rebuild layer hierarchy from scratch and verify that it matches the updated state.
+        LayerHierarchyBuilder newBuilder(mLifecycleManager.getLayers());
+        EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()),
+                  getTraversalPath(newBuilder.getHierarchy()));
+        EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()),
+                  getTraversalPathInZOrder(newBuilder.getHierarchy()));
+        EXPECT_FALSE(
+                mLifecycleManager.getGlobalChanges().test(RequestedLayerState::Changes::Hierarchy));
+    }
+
+    void setZ(uint32_t id, int32_t z) {
+        std::vector<TransactionState> transactions;
+        transactions.emplace_back();
+        transactions.back().states.push_back({});
+
+        transactions.back().states.front().state.what = layer_state_t::eLayerChanged;
+        transactions.back().states.front().state.layerId = static_cast<int32_t>(id);
+        transactions.back().states.front().state.z = z;
+        mLifecycleManager.applyTransactions(transactions);
+    }
+    LayerLifecycleManager mLifecycleManager;
+    std::unordered_map<uint32_t, sp<LayerHandle>> mHandles;
+};
+
+// reparenting tests
+TEST_F(LayerHierarchyTest, addLayer) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+
+    createRootLayer(3);
+    createLayer(112, 11);
+    createLayer(12211, 1221);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+    expectedTraversalPath = {1, 11, 111, 112, 12, 121, 122, 1221, 12211, 13, 2, 3};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, reparentLayer) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    reparentLayer(2, 11);
+    reparentLayer(111, 12);
+    reparentLayer(1221, 1);
+    reparentLayer(1221, 13);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1, 11, 2, 12, 111, 121, 122, 13, 1221};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, reparentLayerToNull) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+    reparentLayer(2, UNASSIGNED_LAYER_ID);
+    reparentLayer(11, UNASSIGNED_LAYER_ID);
+    reparentLayer(1221, 13);
+    reparentLayer(1221, UNASSIGNED_LAYER_ID);
+
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1, 12, 121, 122, 13};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {2, 11, 111, 1221};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, reparentLayerToNullAndDestroyHandles) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    reparentLayer(2, UNASSIGNED_LAYER_ID);
+    reparentLayer(11, UNASSIGNED_LAYER_ID);
+    reparentLayer(1221, UNASSIGNED_LAYER_ID);
+
+    destroyLayerHandle(2);
+    destroyLayerHandle(11);
+    destroyLayerHandle(1221);
+
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1, 12, 121, 122, 13};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {111};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, destroyHandleThenDestroyParentLayer) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    destroyLayerHandle(111);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    // handle is destroyed but layer is kept alive and reachable by parent
+    std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+
+    // destroy parent layer and the child gets destroyed
+    reparentLayer(11, UNASSIGNED_LAYER_ID);
+    destroyLayerHandle(11);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    expectedTraversalPath = {1, 12, 121, 122, 1221, 13, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, layerSurvivesTemporaryReparentToNull) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    reparentLayer(11, UNASSIGNED_LAYER_ID);
+    reparentLayer(11, 1);
+
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+// offscreen tests
+TEST_F(LayerHierarchyTest, layerMovesOnscreen) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+    reparentLayer(11, UNASSIGNED_LAYER_ID);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    reparentLayer(11, 1);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, addLayerToOffscreenParent) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+    reparentLayer(11, UNASSIGNED_LAYER_ID);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    createLayer(112, 11);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1, 12, 121, 122, 1221, 13, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {11, 111, 112};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+// rel-z tests
+TEST_F(LayerHierarchyTest, setRelativeParent) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    reparentRelativeLayer(11, 2);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2, 11, 111};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {1, 12, 121, 122, 1221, 13, 2, 11, 111};
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, reparentFromRelativeParentWithSetLayer) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    reparentRelativeLayer(11, 2);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    reparentRelativeLayer(11, UNASSIGNED_LAYER_ID);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, reparentToRelativeParent) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    reparentRelativeLayer(11, 2);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    reparentLayer(11, 2);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1, 12, 121, 122, 1221, 13, 2, 11, 111};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, setParentAsRelativeParent) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    reparentLayer(11, 2);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    reparentRelativeLayer(11, 2);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1, 12, 121, 122, 1221, 13, 2, 11, 111};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, relativeChildMovesOffscreenIsNotTraversable) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    reparentRelativeLayer(11, 2);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    reparentLayer(2, UNASSIGNED_LAYER_ID);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {1, 12, 121, 122, 1221, 13};
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {2, 11, 111};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+// mirror tests
+TEST_F(LayerHierarchyTest, canTraverseMirrorLayer) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+    mirrorLayer(/*layer*/ 14, /*parent*/ 1, /*layerToMirror*/ 11);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1,    11, 111, 12, 121, 122,
+                                                   1221, 13, 14,  11, 111, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, canMirrorOffscreenLayer) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+    reparentLayer(11, UNASSIGNED_LAYER_ID);
+    mirrorLayer(/*layer*/ 14, /*parent*/ 1, /*layerToMirror*/ 11);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1, 12, 121, 122, 1221, 13, 14, 11, 111, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {11, 111};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, newChildLayerIsUpdatedInMirrorHierarchy) {
+    mirrorLayer(/*layer*/ 14, /*parent*/ 1, /*layerToMirror*/ 11);
+    mLifecycleManager.commitChanges();
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+    createLayer(1111, 111);
+    createLayer(112, 11);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1,    11, 111, 1111, 112, 12,   121, 122,
+                                                   1221, 13, 14,  11,   111, 1111, 112, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+// mirror & relatives tests
+TEST_F(LayerHierarchyTest, mirrorWithRelativeOutsideMirrorHierarchy) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    reparentRelativeLayer(111, 12);
+    mirrorLayer(/*layer*/ 14, /*parent*/ 1, /*layerToMirror*/ 11);
+
+    // ROOT
+    // ├── 1
+    // │   ├── 11
+    // │   │   └── 111
+    // │   ├── 12
+    // │   │   ├── 121
+    // │   │   ├── 122
+    // │   │   │   └── 1221
+    // │   │   └ - 111 (relative)
+    // │   ├── 13
+    // │   └── 14
+    // │       └ * 11 (mirroring)
+    // └── 2
+
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1,    11, 111, 12, 111, 121, 122,
+                                                   1221, 13, 14,  11, 111, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    // 111 is not reachable in the mirror
+    expectedTraversalPath = {1, 11, 12, 111, 121, 122, 1221, 13, 14, 11, 2};
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, mirrorWithRelativeInsideMirrorHierarchy) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    reparentRelativeLayer(1221, 12);
+    mirrorLayer(/*layer*/ 14, /*parent*/ 1, /*layerToMirror*/ 12);
+
+    // ROOT
+    // ├── 1
+    // │   ├── 11
+    // │   │   └── 111
+    // │   ├── 12
+    // │   │   ├── 121
+    // │   │   ├── 122
+    // │   │   │   └── 1221
+    // │   │   └ - 1221 (relative)
+    // │   ├── 13
+    // │   └── 14
+    // │       └ * 12 (mirroring)
+    // └── 2
+
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+    std::vector<uint32_t> expectedTraversalPath = {1,  11, 111, 12,  121, 122,  1221, 1221,
+                                                   13, 14, 12,  121, 122, 1221, 1221, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    // relative layer 1221 is traversable in the mirrored hierarchy as well
+    expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 14, 12, 121, 122, 1221, 2};
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, childMovesOffscreenWhenRelativeParentDies) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+    reparentRelativeLayer(11, 2);
+    reparentLayer(2, UNASSIGNED_LAYER_ID);
+    destroyLayerHandle(2);
+
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+    std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {1, 12, 121, 122, 1221, 13};
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {11, 111};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+
+    // remove relative parent so layer becomes onscreen again
+    reparentRelativeLayer(11, UNASSIGNED_LAYER_ID);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, offscreenLayerCannotBeRelativeToOnscreenLayer) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    reparentRelativeLayer(1221, 2);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    // verify relz path
+    std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2, 1221};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {1, 11, 111, 12, 121, 122, 13, 2, 1221};
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+
+    // offscreen layer cannot be reached as a relative child
+    reparentLayer(12, UNASSIGNED_LAYER_ID);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    expectedTraversalPath = {1, 11, 111, 13, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {12, 121, 122, 1221};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+
+    // layer when onscreen can be reached as a relative child again
+    reparentLayer(12, 1);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13, 2, 1221};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {1, 11, 111, 12, 121, 122, 13, 2, 1221};
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, backgroundLayersAreBehindParentLayer) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+    updateBackgroundColor(1, 0.5);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {1, 1222, 11, 111, 12, 121, 122, 1221, 13, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {1222, 1, 11, 111, 12, 121, 122, 1221, 13, 2};
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+// cycle tests
+TEST_F(LayerHierarchyTest, ParentBecomesTheChild) {
+    // remove default hierarchy
+    mLifecycleManager = LayerLifecycleManager();
+    createRootLayer(1);
+    createLayer(11, 1);
+    reparentLayer(1, 11);
+    mLifecycleManager.commitChanges();
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+    std::vector<uint32_t> expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, RelativeLoops) {
+    // remove default hierarchy
+    mLifecycleManager = LayerLifecycleManager();
+    createRootLayer(1);
+    createRootLayer(2);
+    createLayer(11, 1);
+    reparentRelativeLayer(11, 2);
+    reparentRelativeLayer(2, 11);
+    mLifecycleManager.commitChanges();
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+    // fix loop
+    uint32_t invalidRelativeRoot;
+    bool hasRelZLoop = hierarchyBuilder.getHierarchy().hasRelZLoop(invalidRelativeRoot);
+    EXPECT_TRUE(hasRelZLoop);
+    mLifecycleManager.fixRelativeZLoop(invalidRelativeRoot);
+    hierarchyBuilder.update(mLifecycleManager.getLayers(), mLifecycleManager.getDestroyedLayers());
+    EXPECT_EQ(invalidRelativeRoot, 11u);
+    EXPECT_FALSE(hierarchyBuilder.getHierarchy().hasRelZLoop(invalidRelativeRoot));
+
+    std::vector<uint32_t> expectedTraversalPath = {1, 11, 2, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {1};
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {11, 2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, IndirectRelativeLoops) {
+    // remove default hierarchy
+    mLifecycleManager = LayerLifecycleManager();
+    createRootLayer(1);
+    createRootLayer(2);
+    createLayer(11, 1);
+    createLayer(111, 11);
+    createLayer(21, 2);
+    createLayer(22, 2);
+    createLayer(221, 22);
+    reparentRelativeLayer(22, 111);
+    reparentRelativeLayer(11, 221);
+    mLifecycleManager.commitChanges();
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+
+    // fix loop
+    uint32_t invalidRelativeRoot;
+    bool hasRelZLoop = hierarchyBuilder.getHierarchy().hasRelZLoop(invalidRelativeRoot);
+    EXPECT_TRUE(hasRelZLoop);
+    mLifecycleManager.fixRelativeZLoop(invalidRelativeRoot);
+    hierarchyBuilder.update(mLifecycleManager.getLayers(), mLifecycleManager.getDestroyedLayers());
+    EXPECT_FALSE(hierarchyBuilder.getHierarchy().hasRelZLoop(invalidRelativeRoot));
+
+    std::vector<uint32_t> expectedTraversalPath = {1, 11, 111, 22, 221, 2, 21, 22, 221};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {1, 2, 21};
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {11, 111, 22, 221};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, ReparentRootLayerToNull) {
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    reparentLayer(1, UNASSIGNED_LAYER_ID);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {2};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    expectedTraversalPath = {1, 11, 111, 12, 121, 122, 1221, 13};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+TEST_F(LayerHierarchyTest, AddRemoveLayerInSameTransaction) {
+    // remove default hierarchy
+    mLifecycleManager = LayerLifecycleManager();
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    createRootLayer(1);
+    destroyLayerHandle(1);
+    UPDATE_AND_VERIFY(hierarchyBuilder);
+
+    std::vector<uint32_t> expectedTraversalPath = {};
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPathInZOrder(hierarchyBuilder.getHierarchy()), expectedTraversalPath);
+    EXPECT_EQ(getTraversalPath(hierarchyBuilder.getOffscreenHierarchy()), expectedTraversalPath);
+}
+
+// traversal path test
+TEST_F(LayerHierarchyTest, traversalPathId) {
+    setZ(122, -1);
+    LayerHierarchyBuilder hierarchyBuilder(mLifecycleManager.getLayers());
+    auto checkTraversalPathIdVisitor =
+            [](const LayerHierarchy& hierarchy,
+               const LayerHierarchy::TraversalPath& traversalPath) -> bool {
+        EXPECT_EQ(hierarchy.getLayer()->id, traversalPath.id);
+        return true;
+    };
+    hierarchyBuilder.getHierarchy().traverse(checkTraversalPathIdVisitor);
+    hierarchyBuilder.getHierarchy().traverseInZOrder(checkTraversalPathIdVisitor);
+}
+
+} // namespace android::surfaceflinger::frontend