How to organize binary tree in database? Here is the situation, I need to organize some users like an binary tree to explain organization workflow, but organization can change.

Here is how its look like:

         1
      /     \
     2       3
    / \     / \
   4   5   6   7


Its sounds easy:

Lets imagine this is the user table:

id | user  | position | who_contracted
1  | ana   | 1        | null
2  | bob   | 2        | 1
3  | joe   | 3        | 1
4  | Nik   | 6        | 3
5  | Ahn   | 4        | 1
6  | Rob   | 5        | 2
7  | Chloe | 7        | 1


Ana contracted 4 people in organization, IDs [2,3,5,7]
They are organized as they come to business.

But, when Ana was inviting they, Joe[3] invited Awn[5] to business. Its seat goes to be seat [6].

When Ana[1] invite 1 more, the next opened seat is 4, because each invited people get first seat from left to right down the user who contracted him

It makes easy to build an strong sales team.

Now, I need to know how to find next seat to user in position 3.

I know how to do it with math, but do not know how to organize correctly the database.

For sample, if User id 3 invite one more, will get the seat 12, but if user id 6, invite first, seat will be 12 also.

I need to calculate just in time when insert into table.

Any ideas??

ps. One more thing, I'm trying a way, that if I delete user 3, the users down come to up automatically, user on seat 6 will up to seat 3, because it is on low position compared with next user position, that is 7.
I think this question is principally, "how do you incentivize salesmen in a pyramid scheme?" That's cute, so yeah let's do it. Let's assume


We have 7 people in our scheme.
We allocate bonuses based on the tier of pyramid.


You don't have to place them in a visual pyramid to figure this out..

CREATE TABLE my_pyramid_scheme(empid, name, is_active)
AS
  SELECT id::int, (id+64)::int::"char", true
  FROM generate_series(1,7) AS gs(id);


Now you've got

 empid | name | is_active 
-------+------+-----------
     1 | A    | t
     2 | B    | t
     3 | C    | t
     4 | D    | t
     5 | E    | t
     6 | F    | t
     7 | G    | t


So first we need to know what tier they're on... For that we use 2n-1. For example, if your number is 1.

2n-1 = 1
2n = 2
n = 1 -- you're on tier one


Now if your number is 6

2n-1 = 6
2n = 7
n = 3.5 -- trunc(3.5) you're on tier three.


So after you know what tier they're on. You need to find how much of a bonus they get.. That's a function of the tier they're on, and the maximum amount of tiers, to find that take the largest number and run it through the same process. With those two things, you typically have some geometric function that determines "incentive."

And, now you can run illicit drug cartel or compete with Herbalife.

Disabling members

If in the above you ever set is_active = false run these super fast operations on the row_number..

SELECT *, row_number() OVER (ORDER BY empid) AS newid
FROM my_pyramid_scheme;