gistfile1.php

<?php
namespace cms\entity;

class Category
{

    protected $id;

    protected $left = 0;
    protected $right = 1;

    protected $parent_id = 0;
    protected $order = 0;

    protected $title;

    /** @var array|Category[] */
    public $children = array();

    public function __construct($iArr = array())
    {
        foreach (get_object_vars($this) as $field => $value) {
            if (array_key_exists($field, $iArr)) {
                $this->$field = $iArr[$field];
            }
        }
    }

    public function parentify()
    {
        $tArr = $this->gather(array($this->id => &$this), 'id');

        uasort(
            $tArr, function (Category $a, Category $b) {
                return $a->order - $b->order;
            }
        );

        $uArr = array();
        foreach ($tArr as $i => &$category) {
            if (!$category->id) {
                unset($category);
                continue;
            }

            if (isset($tArr[$category->parent_id])) {
                $tArr[$category->parent_id]->children[] = & $category;
                $uArr[] = $i;
            }

            unset($category);
        }

        foreach ($uArr as $i) {
            unset($tArr[$i]);
        }

        return $this;
    }

    public function nestify()
    {
        $tArr = $this->gather(array($this->left => $this), 'left');

        $lft = & $this->left;
        $rgt = & $this->right;

        uasort(
            $tArr, function (Category $a, Category $b) use (&$lft, &$rgt) {
                $lft = (int) min($lft, $a->left, $b->left);
                $rgt = (int) max($rgt, $a->right, $b->right);

                return $a->left - $b->left;
            }
        );

        $this->right++;

        $this->buildSet($this, $tArr);

        return $this;
    }

    protected function buildSet(&$parent, &$tArr)
    {
        $rArr = array();
        while ($category = array_shift($tArr)) {
            if ($category->left > $parent->left && $category->right < $parent->right) {
                $parent->children[] = $category;
            } else {
                $rArr[] = $category;
            }
        }

        $tArr = $rArr;

        foreach ($parent->children as $category) {
            $this->buildSet($category, $parent->children);
            unset($category);
        }
    }

    public function flatten()
    {
        $this->children = $this->gather();

        return $this;
    }

    protected function gather($tArr = array(), $key = null)
    {
        foreach ($this->children as &$category) {
            if ($key) {
                $tArr[$category->$key] = & $category;
            } else {
                $tArr[] = & $category;
            }
            $tArr = $category->gather($tArr, $key);
            unset($category);
        }

        $this->children = array();

        return $tArr;
    }

    public function rebuild(&$i = 0, $parent_id = 0)
    {
        $this->left = $i;

        foreach ($this->children as &$category) {

            $i++;

            $category->parent_id = $parent_id;
            $category->rebuild($i, $category->id);

            unset($category);
        }

        $this->right = ++$i;

        return $this;
    }
}

gistfile2.php

<?php

use cms\entity\Category;

$root = new Category(['id' => 0, ]);
$root->children[] = new Category(['id' => 1, 'parent_id' => 0]);
$root->children[] = new Category(['id' => 2, 'parent_id' => 1]);
$root->children[] = new Category(['id' => 3, 'parent_id' => 0]);
$root->children[] = new Category(['id' => 4, 'parent_id' => 3]);

var_dump($root->parentify()->rebuild());