Propel NestedSet creating Balanced Tree

Question

Hi folks,

I'm trying to use Propel's NestedSet feature. However, I'm missing something about inserting such that the tree is balanced as it is created (i.e. fill it in horizontally).

Say I have these elements:

       root
  r1c1      r1c2
r2c1 r2c2

I want to insert r2c3 as the 1st child of r1c2 (i.e. fill row 2 before starting on row 3).

My first stab at this was to create this function:

function where(User $root,$depth=0)
{
  $num = $root->getNumberOfDescendants();
  if ( $num < 2 )
    return $root;
  foreach($root->getChildren() as $d)
  {
    if ( $d->getNumberOfChildren() < 2 )
    {
      return $d;
    }
  }
  foreach($root->getChildren() as $d)
  {
    return where($d, $depth+1);
  }
}

However, this will insert a child on r2c1, rather at r1c2 as I want.

Is there a way to insert an entry into the tree at the next available spot somehow?

TIA Mike

Answer 1

OK, thanks to http://dev.mysql.com/tech-resources/articles/hierarchical-data.html, I found that this algorithm will do what I want:

function where($root)
{
  $num = $root->getNumberOfDescendants();
  if ( $num < 2 )
    return $root;

  $finder = DbFinder::from('User')->
    where('LeftId','>=',$root->getLeftId())->
    where('RightId','<=',$root->getRightId())->
    whereCustom('user.RightId = user.LeftId + ?',1,'left')->
    whereCustom('user.RightId = user.LeftId + ?',3,'right')->
    combine(array('left','right'),'or')->
    orderBy('ParentId');
    return $finder->findOne();
}

It basically executes this SQL:

SELECT u.*
FROM user u
WHERE u.LEFT_ID >= $left AND u.RIGHT_ID <= $right AND
  (u.RIGHT_ID = u.LEFT_ID+1 OR u.RIGHT_ID = u.LEFT_ID+3)
ORDER BY u.PARENT_ID
LIMIT 1

A leaf has RIGHT=LEFT+1, A node with 1 child has RIGHT=LEFT+3. By adding the ORDER BY u.PARENT_ID, we find the highest node in the tree available. If you use LEFT_ID or RIGHT_ID, it does not balance the tree.