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.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is a materialized path and how does it enable efficient subtree queries?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A materialized path is a denormalized column that stores the full ancestry chain of a node as a string: "/root-id/child-id/grandchild-id/". The subtree query becomes a simple prefix scan: SELECT * FROM Organization WHERE path LIKE ‘/root-id/%’. With a text_pattern_ops index (for LIKE prefix scans), this is O(log N) — Postgres uses the index to find all rows whose path starts with the given prefix without scanning the whole table. This is dramatically faster than a recursive CTE (WITH RECURSIVE) which traverses one level at a time. The tradeoff: on node insert, the path must be computed from the parent’s path (one DB read). On subtree move, all descendant paths must be updated (one bulk UPDATE). For read-heavy tree access patterns — dashboards, permission checks — materialized paths are the right choice.”}},{“@type”:”Question”,”name”:”How do you safely move a subtree to prevent cycles in the organization tree?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Moving org A under org B creates a cycle if B is a descendant of A (A would be both an ancestor and descendant of itself). Detection with materialized paths: before the move, check whether B’s path starts with A’s path. If new_parent.path.startswith(org_to_move.path), the move is invalid — reject with an error. This check is O(1) with string comparison. The subtree UPDATE after a valid move: UPDATE Organization SET path = REPLACE(path, old_path, new_path), parent_id = new_parent_id WHERE org_id = org_to_move_id; UPDATE Organization SET path = REPLACE(path, old_path, new_path) WHERE path LIKE old_path || ‘%’. Run both in one transaction. The REPLACE changes the path prefix for all nodes in the subtree atomically.”}},{“@type”:”Question”,”name”:”How does permission inheritance work in a deep org tree without storing redundant rows?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Storing one permission row per (user, permission, org) for every descendant would explode: if a user is admin of a root org with 10,000 descendants, that is 10,000 rows. Instead, store the permission only at the org where it was granted. At authorization time, extract ancestor IDs from the materialized path (split "/a/b/c/" on "/" to get [a, b, c]), then check OrgPermission WHERE user_id = X AND org_id = ANY([self, ancestor_1, ancestor_2, …]). A single IN query checks all ancestors — O(1) query regardless of tree depth. Index: CREATE INDEX ON OrgPermission (user_id, org_id, permission) for fast lookup. Cache the result in Redis (permission:{user_id}:{org_id}:{permission} EX 300) to avoid repeated DB lookups for the same user navigating the hierarchy.”}},{“@type”:”Question”,”name”:”When should you use Postgres recursive CTEs instead of materialized paths?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Recursive CTEs (WITH RECURSIVE subtree AS (…)) are appropriate when: (1) the tree is small (< 10,000 nodes) and deep traversal is rare; (2) you do not control the schema and cannot add a path column; (3) the tree changes very frequently and keeping paths synchronized is too expensive. Recursive CTEs traverse one level at a time — performance degrades with depth. At depth 10 with 1M nodes, a recursive CTE may scan millions of rows; a materialized path prefix scan is a single index lookup. For Postgres, add CYCLE detection (CYCLE org_id SET is_cycle TO TRUE DEFAULT FALSE) to recursive CTEs to guard against corrupted data with cycles. Use materialized paths for production systems with frequent reads; recursive CTEs for admin tools and reporting queries where latency is less critical.”}},{“@type”:”Question”,”name”:”How do you count total members in a subtree including all child organizations?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The subtree query returns all org_ids under a given root. Then: SELECT COUNT(*) FROM OrgMember WHERE org_id = ANY(subtree_ids) AND … . For an org with 5,000 descendants, this is an IN with 5,000 values — acceptable for infrequent admin queries. For real-time display (member count shown in every dashboard row), pre-aggregate: add a member_count_recursive column to Organization, updated by a trigger or nightly job. Trigger approach: after INSERT/DELETE on OrgMember, walk up the ancestors (using the path) and increment/decrement their member_count_recursive. The nightly job recalculates from scratch: UPDATE Organization o SET member_count_recursive = (SELECT COUNT(*) FROM OrgMember WHERE org_id IN (SELECT org_id FROM Organization WHERE path LIKE o.path || ‘%’)). Schedule during off-peak to avoid locking.”}}]}
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.