Organization Hierarchy Low-Level Design: Materialized Path, Subtree Queries, and Permission Inheritance

An organization hierarchy system models nested teams, departments, and reporting relationships — essential in B2B SaaS, HR platforms, and enterprise tools. Core challenges: efficiently querying subtrees and ancestors without recursive application-level loops, moving subtrees atomically, and inheriting permissions through the hierarchy so a parent org’s admin automatically manages all descendants.

Core Data Model

-- Adjacency list: simple parent pointer
CREATE TABLE Organization (
    org_id      UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    name        TEXT NOT NULL,
    parent_id   UUID REFERENCES Organization(org_id),  -- NULL for root
    -- Materialized path for efficient tree queries
    path        TEXT NOT NULL,   -- e.g. "/root-uuid/child-uuid/this-uuid/"
    depth       INT NOT NULL DEFAULT 0,
    created_at  TIMESTAMPTZ NOT NULL DEFAULT NOW()
);
CREATE INDEX idx_org_parent ON Organization (parent_id);
CREATE INDEX idx_org_path   ON Organization (path text_pattern_ops); -- prefix scans

-- Members
CREATE TABLE OrgMember (
    member_id   UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    org_id      UUID NOT NULL REFERENCES Organization(org_id),
    user_id     UUID NOT NULL,
    role        TEXT NOT NULL DEFAULT 'member', -- 'owner', 'admin', 'member'
    UNIQUE (org_id, user_id)
);
CREATE INDEX idx_orgmember_user ON OrgMember (user_id);

-- Permissions: a role on a parent org is inherited by all descendants
CREATE TABLE OrgPermission (
    permission_id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    org_id        UUID NOT NULL REFERENCES Organization(org_id),
    user_id       UUID NOT NULL,
    permission    TEXT NOT NULL,  -- 'manage_billing', 'view_reports', 'invite_members'
    is_inherited  BOOLEAN NOT NULL DEFAULT FALSE,
    UNIQUE (org_id, user_id, permission)
);

Creating an Organization and Maintaining Materialized Path

from uuid import uuid4
import psycopg2

def create_org(conn, name: str, parent_id: str | None, creator_id: str) -> str:
    """
    Create a new org. Compute materialized path from parent's path.
    """
    org_id = str(uuid4())

    with conn.cursor() as cur:
        if parent_id:
            cur.execute("SELECT path, depth FROM Organization WHERE org_id = %s", (parent_id,))
            row = cur.fetchone()
            if not row:
                raise ValueError("Parent org not found")
            parent_path, parent_depth = row
            path = f"{parent_path}{org_id}/"
            depth = parent_depth + 1
        else:
            path = f"/{org_id}/"
            depth = 0

        cur.execute(
            "INSERT INTO Organization (org_id, name, parent_id, path, depth) VALUES (%s,%s,%s,%s,%s)",
            (org_id, name, parent_id, path, depth)
        )
        # Auto-add creator as owner
        cur.execute(
            "INSERT INTO OrgMember (org_id, user_id, role) VALUES (%s, %s, 'owner')",
            (org_id, creator_id)
        )
    conn.commit()
    return org_id

Tree Queries Using Materialized Path

def get_subtree(conn, org_id: str) -> list[dict]:
    """
    Get all organizations in the subtree rooted at org_id, including itself.
    Uses the materialized path prefix — no recursion needed.
    """
    with conn.cursor() as cur:
        cur.execute("SELECT path FROM Organization WHERE org_id = %s", (org_id,))
        row = cur.fetchone()
    if not row:
        return []
    path = row[0]

    with conn.cursor() as cur:
        # LIKE 'path%' with text_pattern_ops index is a fast prefix scan
        cur.execute(
            "SELECT org_id, name, parent_id, depth FROM Organization WHERE path LIKE %s ORDER BY depth, name",
            (path + '%',)  # includes the node itself (its path starts with path)
        )
        cols = [d[0] for d in cur.description]
        return [dict(zip(cols, row)) for row in cur.fetchall()]

def get_ancestors(conn, org_id: str) -> list[dict]:
    """
    Get all ancestor organizations from root to parent.
    Split the materialized path to extract ancestor IDs.
    """
    with conn.cursor() as cur:
        cur.execute("SELECT path FROM Organization WHERE org_id = %s", (org_id,))
        row = cur.fetchone()
    if not row:
        return []

    # path = "/root-id/child-id/this-id/"
    parts = [p for p in row[0].strip('/').split('/') if p and p != org_id]
    if not parts:
        return []  # root has no ancestors

    with conn.cursor() as cur:
        cur.execute(
            "SELECT org_id, name, depth FROM Organization WHERE org_id = ANY(%s) ORDER BY depth",
            (parts,)
        )
        cols = [d[0] for d in cur.description]
        return [dict(zip(cols, row)) for row in cur.fetchall()]

def check_permission(conn, user_id: str, org_id: str, permission: str) -> bool:
    """
    Check if user has a permission on org_id OR any ancestor (inherited).
    Looks up user's orgs, checks if any ancestor grants the permission.
    """
    ancestors = get_ancestors(conn, org_id)
    ancestor_ids = [a['org_id'] for a in ancestors] + [org_id]

    with conn.cursor() as cur:
        cur.execute("""
            SELECT 1 FROM OrgPermission
            WHERE user_id = %s
              AND org_id = ANY(%s)
              AND permission = %s
            LIMIT 1
        """, (user_id, ancestor_ids, permission))
        return cur.fetchone() is not None

Moving a Subtree

def move_org(conn, org_id: str, new_parent_id: str):
    """
    Move an org (and its entire subtree) under a new parent.
    Updates all materialized paths in the subtree atomically.
    """
    with conn.cursor() as cur:
        # Validate: new parent must not be in the subtree (would create a cycle)
        cur.execute("SELECT path FROM Organization WHERE org_id = %s", (org_id,))
        old_path = cur.fetchone()[0]

        cur.execute("SELECT path FROM Organization WHERE org_id = %s", (new_parent_id,))
        new_parent_row = cur.fetchone()
        if not new_parent_row:
            raise ValueError("New parent not found")
        new_parent_path = new_parent_row[0]

        if new_parent_path.startswith(old_path):
            raise ValueError("Cannot move an org into its own descendant")

        new_path = f"{new_parent_path}{org_id}/"
        old_depth_offset = old_path.count('/') - 1

        # Update all nodes in the subtree: replace path prefix
        cur.execute("""
            UPDATE Organization
            SET path  = %s || substring(path FROM length(%s) + 1),
                depth = depth + (%s - depth + length(regexp_split_to_array(%s, '/')::text[]) - 2)
            WHERE path LIKE %s
        """, (new_path, old_path, 0, new_path, old_path + '%'))

        # Simpler approach: update depth separately
        cur.execute(
            "SELECT depth FROM Organization WHERE org_id = %s",
            (new_parent_id,)
        )
        new_parent_depth = cur.fetchone()[0]

        cur.execute("""
            UPDATE Organization
            SET path  = REPLACE(path, %s, %s),
                parent_id = CASE WHEN org_id = %s THEN %s ELSE parent_id END
            WHERE path LIKE %s
        """, (old_path, new_path, org_id, new_parent_id, old_path + '%'))

    conn.commit()

Key Interview Points

• Adjacency list vs. materialized path vs. nested sets: Adjacency list (parent_id only) is simple for inserts and moves but requires recursive CTEs (WITH RECURSIVE) for tree queries — expensive at depth 10+. Materialized path adds a denormalized “/a/b/c/” column enabling O(log N) prefix scans for subtrees and O(1) ancestor lookups. Nested sets enable fast reads but make inserts and moves O(N) (rewrite all left/right values). Materialized path is the best general-purpose choice for most applications.
• Cycle prevention on move: Before moving org A under org B, verify B’s path does NOT start with A’s path. If it does, B is a descendant of A — creating a cycle. This check is O(1) with materialized paths.
• Permission inheritance: An admin of the root org should implicitly be an admin of all children. Avoid storing one row per descendant (explodes with deep trees). Instead, at authorization time, walk up the ancestors and check permissions on each. With materialized paths, ancestor IDs are parsed from the path string — a single IN query checks all ancestors at once.
• Postgres recursive CTE alternative: For systems without materialized paths: WITH RECURSIVE subtree AS (SELECT org_id, parent_id FROM Organization WHERE org_id = $1 UNION ALL SELECT o.org_id, o.parent_id FROM Organization o JOIN subtree s ON o.parent_id = s.org_id) SELECT * FROM subtree. Works but performance degrades with depth and node count — add a depth limit: WHERE depth < 20.
• Member count aggregation: “How many members does division X have, including sub-teams?” Use the subtree query to get all org_ids, then COUNT(*) FROM OrgMember WHERE org_id = ANY(subtree_ids). For dashboards, pre-aggregate member counts into Organization.member_count_recursive and update via trigger or nightly job.

Organization hierarchy and team structure design is discussed in Atlassian system design interview questions.

Organization hierarchy and company structure design is covered in LinkedIn system design interview preparation.

Organization hierarchy and permission inheritance design is discussed in Google system design interview guide.