How do you store a tree structure (for example an organizational chart or a category tree) in a relational table using a self-referencing foreign key, and how do you retrieve a whole subtree from it?
answer
- parent_id self-FK, NULL = root
- one row = one edge
- subtree needs recursive CTE
- cheap writes, expensive reads
- FK allows cycles — guard moves
basics
~20 sGive the table a parent_id column that is a foreign key back to its own primary key. Roots have NULL parent_id. One row per node stores one edge. To read a whole subtree you walk the parent_id chain repeatedly, which in standard SQL means a recursive query.
solid answer
~50 sThe standard shape is the **adjacency list**: the table has its own primary key plus a nullable `parent_id` that is a foreign key referencing the same table. Root nodes have `parent_id IS NULL`. Each row records exactly one edge (child → parent), so inserts, moves and deletes touch a single row — a move is one UPDATE of `parent_id`. The cost is reads. A direct query only gives you one level; getting a whole subtree or a full ancestor path requires walking the chain. Standard SQL does that with a recursive common table expression that seeds on the starting node and repeatedly joins children onto the previous level. That means one index lookup per level, so cost grows with tree depth, and the number of round trips grows if the application loops instead. Practical extras: index `parent_id`, decide on the FK's delete behaviour (cascade vs restrict), and guard against cycles — the FK alone will not prevent a node becoming its own ancestor.
code
sql · 7 linesCREATE TABLE category (
id BIGINT PRIMARY KEY,
parent_id BIGINT NULL REFERENCES category(id) ON DELETE RESTRICT,
name VARCHAR(200) NOT NULL
);
CREATE INDEX idx_category_parent ON category(parent_id);go deeper
Be able to draw the table: id, nullable parent_id self-FK, NULL means root — and say that reading a whole subtree needs a recursive query, not a single join.
Add the mechanics: the two halves of a recursive CTE, the index on parent_id, the per-level cost, and the delete-rule choice.
Talk about failure modes in production — cycles from bad moves, unbounded recursion, N+1 traversal from the ORM, and when the read pattern justifies a derived structure.
Frame it as a write-cost vs read-cost decision across the whole workload, and discuss keeping the adjacency list as the source of truth with a derived closure table or path column maintained transactionally.
## What an adjacency list is A hierarchy is data where rows point at other rows of the same kind: an employee reports to an employee, a category sits under a category, a comment replies to a comment. The relational way to express that is a **self-referencing foreign key**, commonly called the *adjacency list* model. The table has a primary key (say `id`) and a nullable column `parent_id` declared as a foreign key referencing `id` of the same table. Every row stores exactly one edge: "my parent is that row". Root nodes store NULL, meaning "no parent". Nullability matters. If `parent_id` were NOT NULL there would be no way to represent a root, because the FK requires the referenced row to exist and the top of the tree has nothing above it. A NULL foreign key is not checked by the constraint, so it is the natural root marker. ## Why reads are the hard part The adjacency list stores only *direct* relationships. A single query with a single join gets you children, or grandchildren if you join twice, but a subtree of unknown depth cannot be expressed by a fixed number of joins. Relational algebra has no fixed-arity operator for transitive closure, which is exactly what a subtree is. SQL solves this with a **recursive common table expression** (recursive CTE), standardized as `WITH RECURSIVE`. It has two halves joined by UNION ALL: an *anchor* query that selects the starting rows, and a *recursive* query that joins the table to the rows produced by the previous iteration. The engine iterates until an iteration produces no rows. Descending a tree seeds on the subtree root and joins `child.parent_id = previous.id`; walking upward to ancestors seeds on the node and joins `parent.id = previous.parent_id`. Each iteration is an index lookup on `parent_id` (index it — without one each level is a full scan). So a subtree read costs roughly one index range scan per level, and the total rows touched equal the subtree size. That is acceptable for shallow trees and for subtrees you actually need in full. It becomes painful when you repeatedly ask "is X anywhere under Y?" or "give me every leaf under the root", and worse if the application issues one query per level in a loop — the classic N+1 pattern against a hierarchy. ## Depth, ordering and extra columns A recursive traversal usually carries a computed `depth` (anchor emits 0, recursive step emits `depth + 1`) and often an accumulated path array or string used for sorting siblings in tree order. Many engines let you `ORDER BY` that accumulated path to render an indented tree in one pass. Depth also gives you a cheap safety valve: adding `WHERE depth < 50` bounds a runaway traversal. ## Cycles and integrity The foreign key guarantees the parent exists; it does **not** guarantee the graph is a tree. `UPDATE node SET parent_id = <one of my own descendants>` produces a cycle, and a naive recursive query over a cycle loops until the engine's recursion limit or memory gives out. Defences, roughly in order of strength: application-level checks before a move (walk the ancestors and refuse if the new parent is a descendant), a trigger doing the same inside the transaction, a cycle-detection clause in the traversal itself (accumulate visited ids and stop when a node repeats — some engines expose `CYCLE ... SET ... TO ... DEFAULT`), or a materialized structure such as a closure table where a cycle is impossible to insert consistently. Deletes need a decision too. `ON DELETE CASCADE` on the self-FK deletes an entire subtree when the parent goes — convenient but easy to fire accidentally. `ON DELETE RESTRICT` forces callers to handle children explicitly. `ON DELETE SET NULL` promotes children to roots, which is almost never what a business wants for a category tree. ## Where it fits among the alternatives The adjacency list is the write-optimal end of the spectrum: insert, delete and *move* are all single-row operations, and a subtree move is O(1) because you only change one edge. Materialized path, nested sets and closure tables all buy faster reads by duplicating structural information, and pay for it on writes. The honest default is: start with the adjacency list plus recursive CTEs, because it is normalized, cheap to maintain and correct by construction; migrate only when a measured read pattern (deep ancestor checks on every request, permission inheritance, huge category trees rendered constantly) proves the traversal is the bottleneck. Some teams keep the adjacency list as the source of truth and add a derived closure table maintained by triggers — the write cost is contained and the read pattern gets its index. ## Practical checklist - `parent_id` nullable, self-FK, indexed. - Explicit delete rule chosen deliberately. - Cycle prevention on the move path. - Traversal via one recursive query, never a per-level application loop. - Depth cap as a safety net on any recursive read.
- Why must the parent_id column be nullable, and what would break if you made it NOT NULL?A root node has no parent, and a foreign key requires the referenced row to exist, so a NOT NULL self-FK makes a root impossible to insert — the first row could never be created. NULL is exempt from foreign-key checking, so it is the natural root marker. Teams that insist on NOT NULL usually resort to a self-referencing root row (id = parent_id), which then needs special handling in every traversal to avoid an infinite loop.
- The foreign key is in place, yet a category ended up as its own ancestor. How did that happen and how do you prevent it?A foreign key only asserts that the referenced parent row exists; it says nothing about the shape of the resulting graph, so an UPDATE that sets a node's parent to one of its own descendants creates a cycle and still satisfies the constraint. Prevention means an explicit check on the move path: walk the ancestors of the proposed new parent and reject if the moved node appears, enforced in a trigger or in the service inside the same transaction. Traversal queries should additionally carry a depth cap or a cycle-detection clause so a bad row degrades to an error rather than a hung query.
- How would you find just the ancestor path of one node rather than its subtree?Flip the direction of the recursive step: seed the anchor on the node itself, then join the table so that the parent row of the previous iteration is produced — `JOIN parent p ON p.id = prev.parent_id`. That walks upward one level per iteration until it reaches the root whose parent_id is NULL. The cost is one primary-key lookup per level, which is why upward walks are usually cheap even in deep trees.
An adjacency list is like everyone in a company knowing only their direct manager's name. Asking "who ultimately reports to the CEO?" means walking up the chain person by person — nobody stores the full chain.
saying these in an interview costs you the question
- Claiming a plain JOIN can return a subtree of arbitrary depth
- Saying the self-referencing foreign key prevents cycles
- Fetching a tree with an application loop issuing one query per level
- Making parent_id NOT NULL and then having no way to represent a root
- Forgetting to index parent_id, turning each recursion level into a full table scan