Representing a binary tree in an SQL table using foreign keys

Question

This is an example of a representation of a binary tree in an SQL table:

     A                                 node  | parent
    / \                                  A   |  NULL
   /   \                                 B   |   A
  /     \                                C   |   A
 B       C                               D   |   B
 |      / \                              E   |   C
 |     /   \                             F   |   C
 D     E    F

As you can see the table tree has two columns: node which is a primary key, and parent which is foreign key. In each node is stored a reference to its parent node. I want to define the same tree but this time using children, each node should reference its children instead. Any idea on how this can be done?

Well, you could just rename column `node` to `child` and column `parent` to `node`, or I am missing something? — GMB, Dec 05 '19 at 23:13
@GMB It would be awkward to store a single-node tree, consisting of the root `node` but no `child` - the only case where you'd store a no-child explicitly. — Bergi, Dec 06 '19 at 00:08
@Bergi - That is why the current implementation is optimal. In fact *I want to have children instead of parents* makes a little sense because a structure is defined by the problem to be solved, not the other way around. — klin, Dec 06 '19 at 00:27
The question should be: I have a problem (description here) that cannot be solved with the current model. How should I change the model? — klin, Dec 06 '19 at 00:36
Does this answer your question? [What are the options for storing hierarchical data in a relational database?](https://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database) — philipxy, Dec 06 '19 at 04:35

score 2 · Answer 1 · answered Dec 05 '19 at 23:26

You'd have some table with three columns. One for an identifier for the node and two for them of its children. So basically something along the lines of:

CREATE TABLE bintree
             (id integer,
              left integer,
              right integer,
              PRIMARY KEY (id),
              FOREIGN KEY (left)
                          REFERENCES bintree
                                     (id),
              FOREIGN KEY (right)
                          REFERENCES bintree
                                     (id));

And maybe a check constraint, that checks that left isn't equal to right and a (constraint) trigger that checks that the thing stays cycle free...

The Impaler · Answer 2 · 2019-12-06T00:21:27.160

Alternatively, you can also define the tree in term of arcs by using two tables

For example:

     A              Table: Nodes       Table: Arcs
    / \             node               parent  | child
   /   \              A                    A   |   B
  /     \             B                    A   |   C
 B       C            C                    B   |   D
 |      / \           D                    C   |   E
 |     /   \          E                    C   |   F
 D     E    F         F

This way the a parent can be related to zero, one, or more children.

The SQL script to do this is:

create table nodes (
  id varchar(10) primary key not null
);

create table arcs (
  parent varchar(10) not null,
  child varchar(10) not null,
  constraint uq1 unique (parent, child), -- optional
  foreign key (parent) references nodes (id),
  foreign key (child) references nodes (id)
);

Representing a binary tree in an SQL table using foreign keys

2 Answers2