diff --git a/services/surfaceflinger/Android.bp b/services/surfaceflinger/Android.bp
index b1bd705..9f7a687 100644
--- a/services/surfaceflinger/Android.bp
+++ b/services/surfaceflinger/Android.bp
@@ -157,6 +157,7 @@
         "EventLog/EventLog.cpp",
         "FrontEnd/LayerCreationArgs.cpp",
         "FrontEnd/LayerHandle.cpp",
+        "FrontEnd/LayerHierarchy.cpp",
         "FrontEnd/LayerLifecycleManager.cpp",
         "FrontEnd/RequestedLayerState.cpp",
         "FrontEnd/TransactionHandler.cpp",
diff --git a/services/surfaceflinger/FrontEnd/LayerHierarchy.cpp b/services/surfaceflinger/FrontEnd/LayerHierarchy.cpp
new file mode 100644
index 0000000..db4e8af
--- /dev/null
+++ b/services/surfaceflinger/FrontEnd/LayerHierarchy.cpp
@@ -0,0 +1,472 @@
+/*
+ * 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.
+ */
+
+#define ATRACE_TAG ATRACE_TAG_GRAPHICS
+#undef LOG_TAG
+#define LOG_TAG "LayerHierarchy"
+
+#include "LayerHierarchy.h"
+#include "SwapErase.h"
+
+namespace android::surfaceflinger::frontend {
+
+namespace {
+auto layerZCompare = [](const std::pair<LayerHierarchy*, LayerHierarchy::Variant>& lhs,
+                        const std::pair<LayerHierarchy*, LayerHierarchy::Variant>& rhs) {
+    auto lhsLayer = lhs.first->getLayer();
+    auto rhsLayer = rhs.first->getLayer();
+    if (lhsLayer->layerStack != rhsLayer->layerStack) {
+        return lhsLayer->layerStack.id < rhsLayer->layerStack.id;
+    }
+    if (lhsLayer->z != rhsLayer->z) {
+        return lhsLayer->z < rhsLayer->z;
+    }
+    return lhsLayer->id < rhsLayer->id;
+};
+
+void insertSorted(std::vector<std::pair<LayerHierarchy*, LayerHierarchy::Variant>>& vec,
+                  std::pair<LayerHierarchy*, LayerHierarchy::Variant> value) {
+    auto it = std::upper_bound(vec.begin(), vec.end(), value, layerZCompare);
+    vec.insert(it, std::move(value));
+}
+} // namespace
+
+LayerHierarchy::LayerHierarchy(RequestedLayerState* layer) : mLayer(layer) {}
+
+LayerHierarchy::LayerHierarchy(const LayerHierarchy& hierarchy, bool childrenOnly) {
+    mLayer = (childrenOnly) ? nullptr : hierarchy.mLayer;
+    mChildren = hierarchy.mChildren;
+}
+
+void LayerHierarchy::traverse(const Visitor& visitor,
+                              LayerHierarchy::TraversalPath& traversalPath) const {
+    if (mLayer) {
+        bool breakTraversal = !visitor(*this, traversalPath);
+        if (breakTraversal) {
+            return;
+        }
+    }
+    if (traversalPath.hasRelZLoop()) {
+        LOG_ALWAYS_FATAL("Found relative z loop layerId:%d", traversalPath.invalidRelativeRootId);
+    }
+    for (auto& [child, childVariant] : mChildren) {
+        ScopedAddToTraversalPath addChildToTraversalPath(traversalPath, child->mLayer->id,
+                                                         childVariant);
+        child->traverse(visitor, traversalPath);
+    }
+}
+
+void LayerHierarchy::traverseInZOrder(const Visitor& visitor,
+                                      LayerHierarchy::TraversalPath& traversalPath) const {
+    bool traverseThisLayer = (mLayer != nullptr);
+    for (auto it = mChildren.begin(); it < mChildren.end(); it++) {
+        auto& [child, childVariant] = *it;
+        if (traverseThisLayer && child->getLayer()->z >= 0) {
+            bool breakTraversal = !visitor(*this, traversalPath);
+            if (breakTraversal) {
+                return;
+            }
+            traverseThisLayer = false;
+        }
+        if (childVariant == LayerHierarchy::Variant::Detached) {
+            continue;
+        }
+        ScopedAddToTraversalPath addChildToTraversalPath(traversalPath, child->mLayer->id,
+                                                         childVariant);
+        child->traverseInZOrder(visitor, traversalPath);
+    }
+
+    if (traverseThisLayer) {
+        visitor(*this, traversalPath);
+    }
+}
+
+void LayerHierarchy::addChild(LayerHierarchy* child, LayerHierarchy::Variant variant) {
+    insertSorted(mChildren, {child, variant});
+}
+
+void LayerHierarchy::removeChild(LayerHierarchy* child) {
+    auto it = std::find_if(mChildren.begin(), mChildren.end(),
+                           [child](const std::pair<LayerHierarchy*, Variant>& x) {
+                               return x.first == child;
+                           });
+    if (it == mChildren.end()) {
+        LOG_ALWAYS_FATAL("Could not find child!");
+    }
+    mChildren.erase(it);
+}
+
+void LayerHierarchy::sortChildrenByZOrder() {
+    std::sort(mChildren.begin(), mChildren.end(), layerZCompare);
+}
+
+void LayerHierarchy::updateChild(LayerHierarchy* hierarchy, LayerHierarchy::Variant variant) {
+    auto it = std::find_if(mChildren.begin(), mChildren.end(),
+                           [hierarchy](std::pair<LayerHierarchy*, Variant>& child) {
+                               return child.first == hierarchy;
+                           });
+    if (it == mChildren.end()) {
+        LOG_ALWAYS_FATAL("Could not find child!");
+    } else {
+        it->second = variant;
+    }
+}
+
+const RequestedLayerState* LayerHierarchy::getLayer() const {
+    return mLayer;
+}
+
+std::string LayerHierarchy::getDebugStringShort() const {
+    std::string debug = "LayerHierarchy{";
+    debug += ((mLayer) ? mLayer->getDebugStringShort() : "root") + " ";
+    if (mChildren.empty()) {
+        debug += "no children";
+    } else {
+        debug += std::to_string(mChildren.size()) + " children";
+    }
+    return debug + "}";
+}
+
+std::string LayerHierarchy::getDebugString(const char* prefix) const {
+    std::string debug = prefix + getDebugStringShort();
+    for (auto& [child, childVariant] : mChildren) {
+        std::string childPrefix = "  " + std::string(prefix) + " " + std::to_string(childVariant);
+        debug += "\n" + child->getDebugString(childPrefix.c_str());
+    }
+    return debug;
+}
+
+bool LayerHierarchy::hasRelZLoop(uint32_t& outInvalidRelativeRoot) const {
+    outInvalidRelativeRoot = UNASSIGNED_LAYER_ID;
+    traverse([&outInvalidRelativeRoot](const LayerHierarchy&,
+                                       const LayerHierarchy::TraversalPath& traversalPath) -> bool {
+        if (traversalPath.hasRelZLoop()) {
+            outInvalidRelativeRoot = traversalPath.invalidRelativeRootId;
+            return false;
+        }
+        return true;
+    });
+    return outInvalidRelativeRoot != UNASSIGNED_LAYER_ID;
+}
+
+LayerHierarchyBuilder::LayerHierarchyBuilder(
+        const std::vector<std::unique_ptr<RequestedLayerState>>& layers) {
+    mHierarchies.reserve(layers.size());
+    mLayerIdToHierarchy.reserve(layers.size());
+    for (auto& layer : layers) {
+        mHierarchies.emplace_back(std::make_unique<LayerHierarchy>(layer.get()));
+        mLayerIdToHierarchy[layer->id] = mHierarchies.back().get();
+    }
+    for (const auto& layer : layers) {
+        onLayerAdded(layer.get());
+    }
+    detachHierarchyFromRelativeParent(&mOffscreenRoot);
+}
+
+void LayerHierarchyBuilder::attachToParent(LayerHierarchy* hierarchy) {
+    auto layer = hierarchy->mLayer;
+    LayerHierarchy::Variant type = layer->hasValidRelativeParent()
+            ? LayerHierarchy::Variant::Detached
+            : LayerHierarchy::Variant::Attached;
+
+    LayerHierarchy* parent;
+
+    if (layer->parentId != UNASSIGNED_LAYER_ID) {
+        parent = getHierarchyFromId(layer->parentId);
+    } else if (layer->canBeRoot) {
+        parent = &mRoot;
+    } else {
+        parent = &mOffscreenRoot;
+    }
+    parent->addChild(hierarchy, type);
+    hierarchy->mParent = parent;
+}
+
+void LayerHierarchyBuilder::detachFromParent(LayerHierarchy* hierarchy) {
+    hierarchy->mParent->removeChild(hierarchy);
+    hierarchy->mParent = nullptr;
+}
+
+void LayerHierarchyBuilder::attachToRelativeParent(LayerHierarchy* hierarchy) {
+    auto layer = hierarchy->mLayer;
+    if (!layer->hasValidRelativeParent() || hierarchy->mRelativeParent) {
+        return;
+    }
+
+    if (layer->relativeParentId != UNASSIGNED_LAYER_ID) {
+        hierarchy->mRelativeParent = getHierarchyFromId(layer->relativeParentId);
+    } else {
+        hierarchy->mRelativeParent = &mOffscreenRoot;
+    }
+    hierarchy->mRelativeParent->addChild(hierarchy, LayerHierarchy::Variant::Relative);
+    hierarchy->mParent->updateChild(hierarchy, LayerHierarchy::Variant::Detached);
+}
+
+void LayerHierarchyBuilder::detachFromRelativeParent(LayerHierarchy* hierarchy) {
+    if (hierarchy->mRelativeParent) {
+        hierarchy->mRelativeParent->removeChild(hierarchy);
+    }
+    hierarchy->mRelativeParent = nullptr;
+    hierarchy->mParent->updateChild(hierarchy, LayerHierarchy::Variant::Attached);
+}
+
+void LayerHierarchyBuilder::attachHierarchyToRelativeParent(LayerHierarchy* root) {
+    if (root->mLayer) {
+        attachToRelativeParent(root);
+    }
+    for (auto& [child, childVariant] : root->mChildren) {
+        if (childVariant == LayerHierarchy::Variant::Detached ||
+            childVariant == LayerHierarchy::Variant::Attached) {
+            attachHierarchyToRelativeParent(child);
+        }
+    }
+}
+
+void LayerHierarchyBuilder::detachHierarchyFromRelativeParent(LayerHierarchy* root) {
+    if (root->mLayer) {
+        detachFromRelativeParent(root);
+    }
+    for (auto& [child, childVariant] : root->mChildren) {
+        if (childVariant == LayerHierarchy::Variant::Detached ||
+            childVariant == LayerHierarchy::Variant::Attached) {
+            detachHierarchyFromRelativeParent(child);
+        }
+    }
+}
+
+void LayerHierarchyBuilder::onLayerAdded(RequestedLayerState* layer) {
+    LayerHierarchy* hierarchy = getHierarchyFromId(layer->id);
+    attachToParent(hierarchy);
+    attachToRelativeParent(hierarchy);
+
+    if (layer->mirrorId != UNASSIGNED_LAYER_ID) {
+        LayerHierarchy* mirror = getHierarchyFromId(layer->mirrorId);
+        hierarchy->addChild(mirror, LayerHierarchy::Variant::Mirror);
+    }
+}
+
+void LayerHierarchyBuilder::onLayerDestroyed(RequestedLayerState* layer) {
+    LayerHierarchy* hierarchy = getHierarchyFromId(layer->id, /*crashOnFailure=*/false);
+    if (!hierarchy) {
+        // Layer was never part of the hierarchy if it was created and destroyed in the same
+        // transaction.
+        return;
+    }
+    // detach from parent
+    detachFromRelativeParent(hierarchy);
+    detachFromParent(hierarchy);
+
+    // detach children
+    for (auto& [child, variant] : hierarchy->mChildren) {
+        if (variant == LayerHierarchy::Variant::Attached ||
+            variant == LayerHierarchy::Variant::Detached) {
+            mOffscreenRoot.addChild(child, LayerHierarchy::Variant::Attached);
+            child->mParent = &mOffscreenRoot;
+        } else if (variant == LayerHierarchy::Variant::Relative) {
+            mOffscreenRoot.addChild(child, LayerHierarchy::Variant::Attached);
+            child->mRelativeParent = &mOffscreenRoot;
+        }
+    }
+
+    swapErase(mHierarchies, [hierarchy](std::unique_ptr<LayerHierarchy>& layerHierarchy) {
+        return layerHierarchy.get() == hierarchy;
+    });
+    mLayerIdToHierarchy.erase(layer->id);
+}
+
+void LayerHierarchyBuilder::updateMirrorLayer(RequestedLayerState* layer) {
+    LayerHierarchy* hierarchy = getHierarchyFromId(layer->id);
+    auto it = hierarchy->mChildren.begin();
+    while (it != hierarchy->mChildren.end()) {
+        if (it->second == LayerHierarchy::Variant::Mirror) {
+            hierarchy->mChildren.erase(it);
+            break;
+        }
+        it++;
+    }
+
+    if (layer->mirrorId != UNASSIGNED_LAYER_ID) {
+        hierarchy->addChild(getHierarchyFromId(layer->mirrorId), LayerHierarchy::Variant::Mirror);
+    }
+}
+
+void LayerHierarchyBuilder::update(
+        const std::vector<std::unique_ptr<RequestedLayerState>>& layers,
+        const std::vector<std::unique_ptr<RequestedLayerState>>& destroyedLayers) {
+    // rebuild map
+    for (auto& layer : layers) {
+        if (layer->changes.test(RequestedLayerState::Changes::Created)) {
+            mHierarchies.emplace_back(std::make_unique<LayerHierarchy>(layer.get()));
+            mLayerIdToHierarchy[layer->id] = mHierarchies.back().get();
+        }
+    }
+
+    for (auto& layer : layers) {
+        if (layer->changes.get() == 0) {
+            continue;
+        }
+        if (layer->changes.test(RequestedLayerState::Changes::Created)) {
+            onLayerAdded(layer.get());
+            continue;
+        }
+        LayerHierarchy* hierarchy = getHierarchyFromId(layer->id);
+        if (layer->changes.test(RequestedLayerState::Changes::Parent)) {
+            detachFromParent(hierarchy);
+            attachToParent(hierarchy);
+        }
+        if (layer->changes.test(RequestedLayerState::Changes::RelativeParent)) {
+            detachFromRelativeParent(hierarchy);
+            attachToRelativeParent(hierarchy);
+        }
+        if (layer->changes.test(RequestedLayerState::Changes::Z)) {
+            hierarchy->mParent->sortChildrenByZOrder();
+            if (hierarchy->mRelativeParent) {
+                hierarchy->mRelativeParent->sortChildrenByZOrder();
+            }
+        }
+        if (layer->changes.test(RequestedLayerState::Changes::Mirror)) {
+            updateMirrorLayer(layer.get());
+        }
+    }
+
+    for (auto& layer : destroyedLayers) {
+        onLayerDestroyed(layer.get());
+    }
+    // When moving from onscreen to offscreen and vice versa, we need to attach and detach
+    // from our relative parents. This walks down both trees to do so. We can optimize this
+    // further by tracking onscreen, offscreen state in LayerHierarchy.
+    detachHierarchyFromRelativeParent(&mOffscreenRoot);
+    attachHierarchyToRelativeParent(&mRoot);
+}
+
+const LayerHierarchy& LayerHierarchyBuilder::getHierarchy() const {
+    return mRoot;
+}
+
+const LayerHierarchy& LayerHierarchyBuilder::getOffscreenHierarchy() const {
+    return mOffscreenRoot;
+}
+
+std::string LayerHierarchyBuilder::getDebugString(uint32_t layerId, uint32_t depth) const {
+    if (depth > 10) return "too deep, loop?";
+    if (layerId == UNASSIGNED_LAYER_ID) return "";
+    auto it = mLayerIdToHierarchy.find(layerId);
+    if (it == mLayerIdToHierarchy.end()) return "not found";
+
+    LayerHierarchy* hierarchy = it->second;
+    if (!hierarchy->mLayer) return "none";
+
+    std::string debug =
+            "[" + std::to_string(hierarchy->mLayer->id) + "] " + hierarchy->mLayer->name;
+    if (hierarchy->mRelativeParent) {
+        debug += " Relative:" + hierarchy->mRelativeParent->getDebugStringShort();
+    }
+    if (hierarchy->mParent) {
+        debug += " Parent:" + hierarchy->mParent->getDebugStringShort();
+    }
+    return debug;
+}
+
+LayerHierarchy LayerHierarchyBuilder::getPartialHierarchy(uint32_t layerId,
+                                                          bool childrenOnly) const {
+    auto it = mLayerIdToHierarchy.find(layerId);
+    if (it == mLayerIdToHierarchy.end()) return {nullptr};
+
+    LayerHierarchy hierarchy(*it->second, childrenOnly);
+    return hierarchy;
+}
+
+LayerHierarchy* LayerHierarchyBuilder::getHierarchyFromId(uint32_t layerId, bool crashOnFailure) {
+    auto it = mLayerIdToHierarchy.find(layerId);
+    if (it == mLayerIdToHierarchy.end()) {
+        if (crashOnFailure) {
+            LOG_ALWAYS_FATAL("Could not find hierarchy for layer id %d", layerId);
+        }
+        return nullptr;
+    };
+
+    return it->second;
+}
+
+LayerHierarchy::TraversalPath LayerHierarchy::TraversalPath::ROOT_TRAVERSAL_ID =
+        {.id = UNASSIGNED_LAYER_ID, .variant = LayerHierarchy::Attached};
+
+std::string LayerHierarchy::TraversalPath::toString() const {
+    std::string debugString = "TraversalPath{.id = " + std::to_string(id);
+
+    if (!mirrorRootIds.empty()) {
+        debugString += ", .mirrorRootIds=";
+        for (auto rootId : mirrorRootIds) {
+            debugString += std::to_string(rootId) + ",";
+        }
+    }
+
+    if (!relativeRootIds.empty()) {
+        debugString += ", .relativeRootIds=";
+        for (auto rootId : relativeRootIds) {
+            debugString += std::to_string(rootId) + ",";
+        }
+    }
+
+    if (hasRelZLoop()) {
+        debugString += ", hasRelZLoop=true invalidRelativeRootId=";
+        debugString += std::to_string(invalidRelativeRootId) + ",";
+    }
+
+    debugString += "}";
+    return debugString;
+}
+
+// Helper class to update a passed in TraversalPath when visiting a child. When the object goes out
+// of scope the TraversalPath is reset to its original state.
+LayerHierarchy::ScopedAddToTraversalPath::ScopedAddToTraversalPath(TraversalPath& traversalPath,
+                                                                   uint32_t layerId,
+                                                                   LayerHierarchy::Variant variant)
+      : mTraversalPath(traversalPath),
+        mParentId(traversalPath.id),
+        mParentVariant(traversalPath.variant) {
+    // Update the traversal id with the child layer id and variant. Parent id and variant are
+    // stored to reset the id upon destruction.
+    traversalPath.id = layerId;
+    traversalPath.variant = variant;
+    if (variant == LayerHierarchy::Variant::Mirror) {
+        traversalPath.mirrorRootIds.emplace_back(layerId);
+    }
+    if (variant == LayerHierarchy::Variant::Relative) {
+        if (std::find(traversalPath.relativeRootIds.begin(), traversalPath.relativeRootIds.end(),
+                      layerId) != traversalPath.relativeRootIds.end()) {
+            traversalPath.invalidRelativeRootId = layerId;
+        }
+        traversalPath.relativeRootIds.emplace_back(layerId);
+    }
+}
+LayerHierarchy::ScopedAddToTraversalPath::~ScopedAddToTraversalPath() {
+    // Reset the traversal id to its original parent state using the state that was saved in
+    // the constructor.
+    if (mTraversalPath.variant == LayerHierarchy::Variant::Mirror) {
+        mTraversalPath.mirrorRootIds.pop_back();
+    }
+    if (mTraversalPath.variant == LayerHierarchy::Variant::Relative) {
+        mTraversalPath.relativeRootIds.pop_back();
+    }
+    if (mTraversalPath.invalidRelativeRootId == mTraversalPath.id) {
+        mTraversalPath.invalidRelativeRootId = UNASSIGNED_LAYER_ID;
+    }
+    mTraversalPath.id = mParentId;
+    mTraversalPath.variant = mParentVariant;
+}
+
+} // namespace android::surfaceflinger::frontend
diff --git a/services/surfaceflinger/FrontEnd/LayerHierarchy.h b/services/surfaceflinger/FrontEnd/LayerHierarchy.h
new file mode 100644
index 0000000..f83a859
--- /dev/null
+++ b/services/surfaceflinger/FrontEnd/LayerHierarchy.h
@@ -0,0 +1,163 @@
+/*
+ * 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.
+ */
+
+#pragma once
+
+#include "FrontEnd/LayerCreationArgs.h"
+#include "RequestedLayerState.h"
+#include "ftl/small_vector.h"
+
+namespace android::surfaceflinger::frontend {
+class LayerHierarchyBuilder;
+
+// LayerHierarchy allows us to navigate the layer hierarchy in z-order, or depth first traversal.
+// The hierarchy is created from a set of RequestedLayerStates. The hierarchy itself does not
+// contain additional states. Instead, it is a representation of RequestedLayerStates as a graph.
+//
+// Each node in the hierarchy can be visited by multiple parents (making this a graph). While
+// traversing the hierarchy, a new concept called Variant can be used to understand the
+// relationship of the layer to its parent. The following variants are possible:
+// Attached - child of the parent
+// Detached - child of the parent but currently relative parented to another layer
+// Relative - relative child of the parent
+// Mirror - mirrored from another layer
+//
+// By representing the hierarchy as a graph, we can represent mirrored layer hierarchies without
+// cloning the layer requested state. The mirrored hierarchy and its corresponding
+// RequestedLayerStates are kept in sync because the mirrored hierarchy does not clone any
+// states.
+class LayerHierarchy {
+public:
+    enum Variant {
+        Attached,
+        Detached,
+        Relative,
+        Mirror,
+    };
+    // Represents a unique path to a node.
+    struct TraversalPath {
+        uint32_t id;
+        LayerHierarchy::Variant variant;
+        // Mirrored layers can have a different geometry than their parents so we need to track
+        // the mirror roots in the traversal.
+        ftl::SmallVector<uint32_t, 5> mirrorRootIds;
+        // Relative layers can be visited twice, once by their parent and then once again by
+        // their relative parent. We keep track of the roots here to detect any loops in the
+        // hierarchy. If a relative root already exists in the list while building the
+        // TraversalPath, it means that somewhere in the hierarchy two layers are relatively
+        // parented to each other.
+        ftl::SmallVector<uint32_t, 5> relativeRootIds;
+        // First duplicate relative root id found. If this is a valid layer id that means we are
+        // in a loop.
+        uint32_t invalidRelativeRootId = UNASSIGNED_LAYER_ID;
+        bool hasRelZLoop() const { return invalidRelativeRootId != UNASSIGNED_LAYER_ID; }
+        bool isRelative() { return !relativeRootIds.empty(); }
+
+        bool operator==(const TraversalPath& other) const {
+            return id == other.id && mirrorRootIds == other.mirrorRootIds;
+        }
+        std::string toString() const;
+
+        static TraversalPath ROOT_TRAVERSAL_ID;
+    };
+
+    // Helper class to add nodes to an existing traversal id and removes the
+    // node when it goes out of scope.
+    class ScopedAddToTraversalPath {
+    public:
+        ScopedAddToTraversalPath(TraversalPath& traversalPath, uint32_t layerId,
+                                 LayerHierarchy::Variant variantArg);
+        ~ScopedAddToTraversalPath();
+
+    private:
+        TraversalPath& mTraversalPath;
+        uint32_t mParentId;
+        LayerHierarchy::Variant mParentVariant;
+    };
+    LayerHierarchy(RequestedLayerState* layer);
+
+    // Visitor function that provides the hierarchy node and a traversal id which uniquely
+    // identifies how was visited. The hierarchy contains a pointer to the RequestedLayerState.
+    // Return false to stop traversing down the hierarchy.
+    typedef std::function<bool(const LayerHierarchy& hierarchy,
+                               const LayerHierarchy::TraversalPath& traversalPath)>
+            Visitor;
+
+    // Traverse the hierarchy and visit all child variants.
+    void traverse(const Visitor& visitor) const {
+        traverse(visitor, TraversalPath::ROOT_TRAVERSAL_ID);
+    }
+
+    // Traverse the hierarchy in z-order, skipping children that have relative parents.
+    void traverseInZOrder(const Visitor& visitor) const {
+        traverseInZOrder(visitor, TraversalPath::ROOT_TRAVERSAL_ID);
+    }
+
+    const RequestedLayerState* getLayer() const;
+    std::string getDebugString(const char* prefix = "") const;
+    std::string getDebugStringShort() const;
+    // Traverse the hierarchy and return true if loops are found. The outInvalidRelativeRoot
+    // will contain the first relative root that was visited twice in a traversal.
+    bool hasRelZLoop(uint32_t& outInvalidRelativeRoot) const;
+    std::vector<std::pair<LayerHierarchy*, Variant>> mChildren;
+
+private:
+    friend LayerHierarchyBuilder;
+    LayerHierarchy(const LayerHierarchy& hierarchy, bool childrenOnly);
+    void addChild(LayerHierarchy*, LayerHierarchy::Variant);
+    void removeChild(LayerHierarchy*);
+    void sortChildrenByZOrder();
+    void updateChild(LayerHierarchy*, LayerHierarchy::Variant);
+    void traverseInZOrder(const Visitor& visitor, LayerHierarchy::TraversalPath& parent) const;
+    void traverse(const Visitor& visitor, LayerHierarchy::TraversalPath& parent) const;
+
+    const RequestedLayerState* mLayer;
+    LayerHierarchy* mParent = nullptr;
+    LayerHierarchy* mRelativeParent = nullptr;
+};
+
+// Given a list of RequestedLayerState, this class will build a root hierarchy and an
+// offscreen hierarchy. The builder also has an update method which can update an existing
+// hierarchy from a list of RequestedLayerState and associated change flags.
+class LayerHierarchyBuilder {
+public:
+    LayerHierarchyBuilder(const std::vector<std::unique_ptr<RequestedLayerState>>&);
+    void update(const std::vector<std::unique_ptr<RequestedLayerState>>& layers,
+                const std::vector<std::unique_ptr<RequestedLayerState>>& destroyedLayers);
+    LayerHierarchy getPartialHierarchy(uint32_t, bool childrenOnly) const;
+    const LayerHierarchy& getHierarchy() const;
+    const LayerHierarchy& getOffscreenHierarchy() const;
+    std::string getDebugString(uint32_t layerId, uint32_t depth = 0) const;
+
+private:
+    void onLayerAdded(RequestedLayerState* layer);
+    void attachToParent(LayerHierarchy*);
+    void detachFromParent(LayerHierarchy*);
+    void attachToRelativeParent(LayerHierarchy*);
+    void detachFromRelativeParent(LayerHierarchy*);
+    void attachHierarchyToRelativeParent(LayerHierarchy*);
+    void detachHierarchyFromRelativeParent(LayerHierarchy*);
+
+    void onLayerDestroyed(RequestedLayerState* layer);
+    void updateMirrorLayer(RequestedLayerState* layer);
+    LayerHierarchy* getHierarchyFromId(uint32_t layerId, bool crashOnFailure = true);
+    std::unordered_map<uint32_t, LayerHierarchy*> mLayerIdToHierarchy;
+    std::vector<std::unique_ptr<LayerHierarchy>> mHierarchies;
+    LayerHierarchy mRoot{nullptr};
+    LayerHierarchy mOffscreenRoot{nullptr};
+};
+
+} // namespace android::surfaceflinger::frontend
diff --git a/services/surfaceflinger/FrontEnd/LayerLifecycleManager.cpp b/services/surfaceflinger/FrontEnd/LayerLifecycleManager.cpp
index 1108246..d869ab5 100644
--- a/services/surfaceflinger/FrontEnd/LayerLifecycleManager.cpp
+++ b/services/surfaceflinger/FrontEnd/LayerLifecycleManager.cpp
@@ -42,10 +42,10 @@
                              it->second.owner.getDebugString().c_str());
         }
 
-        linkLayer(layer.parentId, layer.id);
-        linkLayer(layer.relativeParentId, layer.id);
-        linkLayer(layer.mirrorId, layer.id);
-        linkLayer(layer.touchCropId, layer.id);
+        layer.parentId = linkLayer(layer.parentId, layer.id);
+        layer.relativeParentId = linkLayer(layer.relativeParentId, layer.id);
+        layer.mirrorId = linkLayer(layer.mirrorId, layer.id);
+        layer.touchCropId = linkLayer(layer.touchCropId, layer.id);
 
         mLayers.emplace_back(std::move(newLayer));
     }
@@ -83,10 +83,10 @@
 
         RequestedLayerState& layer = it->second.owner;
 
-        unlinkLayer(layer.parentId, layer.id);
-        unlinkLayer(layer.relativeParentId, layer.id);
-        unlinkLayer(layer.mirrorId, layer.id);
-        unlinkLayer(layer.touchCropId, layer.id);
+        layer.parentId = unlinkLayer(layer.parentId, layer.id);
+        layer.relativeParentId = unlinkLayer(layer.relativeParentId, layer.id);
+        layer.mirrorId = unlinkLayer(layer.mirrorId, layer.id);
+        layer.touchCropId = unlinkLayer(layer.touchCropId, layer.id);
 
         auto& references = it->second.references;
         for (uint32_t linkedLayerId : references) {
@@ -195,15 +195,15 @@
 
             if (oldParentId != layer->parentId) {
                 unlinkLayer(oldParentId, layer->id);
-                linkLayer(layer->parentId, layer->id);
+                layer->parentId = linkLayer(layer->parentId, layer->id);
             }
             if (oldRelativeParentId != layer->relativeParentId) {
                 unlinkLayer(oldRelativeParentId, layer->id);
-                linkLayer(layer->relativeParentId, layer->id);
+                layer->relativeParentId = linkLayer(layer->relativeParentId, layer->id);
             }
             if (oldTouchCropId != layer->touchCropId) {
                 unlinkLayer(oldTouchCropId, layer->id);
-                linkLayer(layer->touchCropId, layer->id);
+                layer->touchCropId = linkLayer(layer->touchCropId, layer->id);
             }
 
             mGlobalChanges |= layer->changes &
@@ -283,26 +283,28 @@
     return &it->second.references;
 }
 
-void LayerLifecycleManager::linkLayer(uint32_t layerId, uint32_t layerToLink) {
-    if (layerToLink && layerId != UNASSIGNED_LAYER_ID) {
-        std::vector<uint32_t>* linkedLayers = getLinkedLayersFromId(layerId);
-        if (!linkedLayers) {
-            LOG_ALWAYS_FATAL("Could not find layer id %d to link %d", layerId, layerToLink);
-            return;
-        }
-        linkedLayers->emplace_back(layerToLink);
+uint32_t LayerLifecycleManager::linkLayer(uint32_t layerId, uint32_t layerToLink) {
+    if (layerId == UNASSIGNED_LAYER_ID) {
+        return UNASSIGNED_LAYER_ID;
     }
-}
-
-void LayerLifecycleManager::unlinkLayer(uint32_t& inOutLayerId, uint32_t linkedLayer) {
-    uint32_t layerId = inOutLayerId;
-    inOutLayerId = UNASSIGNED_LAYER_ID;
 
     std::vector<uint32_t>* linkedLayers = getLinkedLayersFromId(layerId);
     if (!linkedLayers) {
-        return;
+        ALOGV("Could not find layer id %d to link %d. Parent is probably destroyed", layerId,
+              layerToLink);
+        return UNASSIGNED_LAYER_ID;
+    }
+    linkedLayers->emplace_back(layerToLink);
+    return layerId;
+}
+
+uint32_t LayerLifecycleManager::unlinkLayer(uint32_t layerId, uint32_t linkedLayer) {
+    std::vector<uint32_t>* linkedLayers = getLinkedLayersFromId(layerId);
+    if (!linkedLayers) {
+        return UNASSIGNED_LAYER_ID;
     }
     swapErase(*linkedLayers, linkedLayer);
+    return UNASSIGNED_LAYER_ID;
 }
 
 std::string LayerLifecycleManager::References::getDebugString() const {
@@ -314,4 +316,16 @@
     return debugInfo;
 }
 
+void LayerLifecycleManager::fixRelativeZLoop(uint32_t relativeRootId) {
+    auto it = mIdToLayer.find(relativeRootId);
+    if (it == mIdToLayer.end()) {
+        return;
+    }
+    RequestedLayerState& layer = it->second.owner;
+    layer.relativeParentId = unlinkLayer(layer.relativeParentId, layer.id);
+    layer.changes |=
+            RequestedLayerState::Changes::Hierarchy | RequestedLayerState::Changes::RelativeParent;
+    mGlobalChanges |= RequestedLayerState::Changes::Hierarchy;
+}
+
 } // namespace android::surfaceflinger::frontend
diff --git a/services/surfaceflinger/FrontEnd/LayerLifecycleManager.h b/services/surfaceflinger/FrontEnd/LayerLifecycleManager.h
index ad70d3f..63a7afc 100644
--- a/services/surfaceflinger/FrontEnd/LayerLifecycleManager.h
+++ b/services/surfaceflinger/FrontEnd/LayerLifecycleManager.h
@@ -42,6 +42,12 @@
     void applyTransactions(const std::vector<TransactionState>&);
     void onHandlesDestroyed(const std::vector<uint32_t>&);
 
+    // Detaches the layer from its relative parent to prevent a loop in the
+    // layer hierarchy. This overrides the RequestedLayerState and leaves
+    // the system in an invalid state. This is always a client error that
+    // needs to be fixed but overriding the state allows us to fail gracefully.
+    void fixRelativeZLoop(uint32_t relativeRootId);
+
     // Destroys RequestedLayerStates that are marked to be destroyed. Invokes all
     // ILifecycleListener callbacks and clears any change flags from previous state
     // updates. This function should be called outside the hot path since it's not
@@ -72,8 +78,8 @@
 
     RequestedLayerState* getLayerFromId(uint32_t);
     std::vector<uint32_t>* getLinkedLayersFromId(uint32_t);
-    void linkLayer(uint32_t layerId, uint32_t layerToLink);
-    void unlinkLayer(uint32_t& inOutLayerId, uint32_t linkedLayer);
+    uint32_t linkLayer(uint32_t layerId, uint32_t layerToLink);
+    uint32_t unlinkLayer(uint32_t layerId, uint32_t linkedLayer);
 
     struct References {
         // Lifetime tied to mLayers
diff --git a/services/surfaceflinger/FrontEnd/RequestedLayerState.cpp b/services/surfaceflinger/FrontEnd/RequestedLayerState.cpp
index 45058d9..e2a4ed1 100644
--- a/services/surfaceflinger/FrontEnd/RequestedLayerState.cpp
+++ b/services/surfaceflinger/FrontEnd/RequestedLayerState.cpp
@@ -40,7 +40,7 @@
 }
 
 std::string layerIdToString(uint32_t layerId) {
-    return layerId == UNASSIGNED_LAYER_ID ? std::to_string(layerId) : "none";
+    return layerId == UNASSIGNED_LAYER_ID ? "none" : std::to_string(layerId);
 }
 
 } // namespace
@@ -147,13 +147,17 @@
         static const mat4 identityMatrix = mat4();
         hasColorTransform = colorTransform != identityMatrix;
     }
-    if (clientState.what & layer_state_t::eLayerChanged) {
+    if (clientState.what & (layer_state_t::eLayerChanged | layer_state_t::eRelativeLayerChanged)) {
         changes |= RequestedLayerState::Changes::Z;
     }
     if (clientState.what & layer_state_t::eReparent) {
         changes |= RequestedLayerState::Changes::Parent;
         parentId = getLayerIdFromSurfaceControl(clientState.parentSurfaceControlForChild);
         parentSurfaceControlForChild = nullptr;
+        // Once a layer has be reparented, it cannot be placed at the root. It sounds odd
+        // but thats the existing logic and until we make this behavior more explicit, we need
+        // to maintain this logic.
+        canBeRoot = false;
     }
     if (clientState.what & layer_state_t::eRelativeLayerChanged) {
         changes |= RequestedLayerState::Changes::RelativeParent;
@@ -254,7 +258,7 @@
             ",relativeParent=" + layerIdToString(relativeParentId) +
             ",isRelativeOf=" + std::to_string(isRelativeOf) +
             ",mirrorId=" + layerIdToString(mirrorId) +
-            ",handleAlive=" + std::to_string(handleAlive);
+            ",handleAlive=" + std::to_string(handleAlive) + ",z=" + std::to_string(z);
 }
 
 std::string RequestedLayerState::getDebugStringShort() const {
@@ -355,4 +359,13 @@
     return Region(win).subtract(exclude).getBounds();
 }
 
+// Returns true if the layer has a relative parent that is not its own parent. This is an input
+// error from the client, and this check allows us to handle it gracefully. If both parentId and
+// relativeParentId is unassigned then the layer does not have a valid relative parent.
+// If the relative parentid is unassigned, the layer will be considered relative but won't be
+// reachable.
+bool RequestedLayerState::hasValidRelativeParent() const {
+    return isRelativeOf && parentId != relativeParentId;
+}
+
 } // namespace android::surfaceflinger::frontend
diff --git a/services/surfaceflinger/FrontEnd/RequestedLayerState.h b/services/surfaceflinger/FrontEnd/RequestedLayerState.h
index 0ddf5e2..6891fbc 100644
--- a/services/surfaceflinger/FrontEnd/RequestedLayerState.h
+++ b/services/surfaceflinger/FrontEnd/RequestedLayerState.h
@@ -62,13 +62,14 @@
     std::string getDebugString() const;
     std::string getDebugStringShort() const;
     aidl::android::hardware::graphics::composer3::Composition getCompositionType() const;
+    bool hasValidRelativeParent() const;
 
     // Layer serial number.  This gives layers an explicit ordering, so we
     // have a stable sort order when their layer stack and Z-order are
     // the same.
     const uint32_t id;
     const std::string name;
-    const bool canBeRoot = false;
+    bool canBeRoot = false;
     const uint32_t layerCreationFlags;
     const uint32_t textureName;
     // The owner of the layer. If created from a non system process, it will be the calling uid.
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