Question

How to parse a table into a binary tree in PHP

Answer 1

/**
 * Parse a table of (Id, Name, ParentId) into a binary tree using
 * the Left‑Child / Right‑Sibling representation.
 *
 * Why this representation?
 * - The table describes a general tree (each node can have many children).
 * - A binary tree requires each node to have at most two pointers.
 * - left  -> first child
 * - right -> next sibling
 *
 * This preserves the full structure while staying inside a binary tree model.
 */

class Node {
    public int $id;
    public string $name;

    public ?Node $left;   // first child
    public ?Node $right;  // next sibling

    public function __construct(int $id, string $name) {
        $this->id   = $id;
        $this->name = $name;
        $this->left = null;
        $this->right = null;
    }
}

/* -------------------- Print Tree -------------------- */

function printTree(?Node $root, int $depth = 0): void {
    if ($root === null) return;

    // Print ROOT on its own line
    if ($depth === 0) {
        echo "ROOT\n";
    }

    // Indent the node itself
    for ($i = 0; $i < $depth + 1; $i++) {
        echo "  ";
    }

    // print ID with leading zero if needed
    printf("%02d - %s\n", $root->id, $root->name);

    // first child
    printTree($root->left, $depth + 1);

    // next sibling (another top-level node)
    if ($depth === 0 && $root->right !== null) {
        printTree($root->right, 0);   // restart ROOT
    } else {
        printTree($root->right, $depth);
    }
}

/* ------------------------------------------------------------
   Build the tree using Left‑Child / Right‑Sibling representation
   ------------------------------------------------------------ */

function buildTree(array $table, array &$nodesOut): ?Node {

    // Create nodes
    foreach ($table as $row) {
        $id   = $row['id'];
        $name = $row['name'];
        $nodesOut[$id] = new Node($id, $name);
    }

    $root = null;

    // Attach children and siblings
    foreach ($table as $row) {
        $id        = $row['id'];
        $parentId  = $row['parentId'];
        $current   = $nodesOut[$id];

        if ($parentId === 0) {
            // top-level node → sibling chain under root
            if ($root === null) {
                $root = $current;
            } else {
                $p = $root;
                while ($p->right !== null) {
                    $p = $p->right;
                }
                $p->right = $current;
            }
        } else {
            $parent = $nodesOut[$parentId];

            // attach as first child or next sibling
            if ($parent->left === null) {
                $parent->left = $current;
            } else {
                $p = $parent->left;
                while ($p->right !== null) {
                    $p = $p->right;
                }
                $p->right = $current;
            }
        }
    }

    return $root;
}

/* -------------------- Main -------------------- */

// Example table
$table = [
    [ 'id' => 1,  'name' => 'Node 1',        'parentId' => 0 ],
    [ 'id' => 2,  'name' => 'Node 1.1',      'parentId' => 1 ],
    [ 'id' => 3,  'name' => 'Node 2',        'parentId' => 0 ],
    [ 'id' => 4,  'name' => 'Node 1.1.1',    'parentId' => 2 ],
    [ 'id' => 5,  'name' => 'Node 2.1',      'parentId' => 3 ],
    [ 'id' => 6,  'name' => 'Node 2.3.1',    'parentId' => 3 ],
    [ 'id' => 7,  'name' => 'Node 1.2',      'parentId' => 1 ],
    [ 'id' => 8,  'name' => 'Node 1.3',      'parentId' => 1 ],
    [ 'id' => 9,  'name' => 'Node 1.3.1',    'parentId' => 8 ],
    [ 'id' => 10, 'name' => 'Node 2.4',      'parentId' => 3 ],
    [ 'id' => 11, 'name' => 'Node 2.1.1',    'parentId' => 5 ],
    [ 'id' => 12, 'name' => 'Node 2.1.1.6',  'parentId' => 11 ],
];

$nodes = [];

// Build tree
$root = buildTree($table, $nodes);

// Print
printTree($root);


 
/*
run:

ROOT
  01 - Node 1
    02 - Node 1.1
      04 - Node 1.1.1
    07 - Node 1.2
    08 - Node 1.3
      09 - Node 1.3.1
ROOT
  03 - Node 2
    05 - Node 2.1
      11 - Node 2.1.1
        12 - Node 2.1.1.6
    06 - Node 2.3.1
    10 - Node 2.4

*/

 

70+ SQL courses for beginners and professionals