Display parents for a specific child id using PHP MySQL

Question

I am trying to display all the parents for a specific child in a chain data as like the below image

For this table data

So far I have tried with the below approaches :

// for this one i am getting a indefinite loop

public function buildBinaryTree($user_id)
{
    $pictures = [];

    $p_info = $this->memberRepository->getMemberInfo($user_id);
    $p_id = $p_info->member_id;

    if(empty($p_id)){
        return;
    }

    $children = $this->buildBinaryTree($p_id);

    if ($children) {
        echo "child ". $p_id."</br>";
    }
}

public function buildTree($all_members, $user_id)
{
    $pictures = [];

    foreach ($all_members as $item) {

        if ($item->member_id == $user_id) {

            $pictures[] = [
                'member_id'      => $item->member_id,
                'referrar_id'     => $item->user_id
            ];

            $children = $this->buildTree($all_members, $item->user_id);

            if ($children) {
                $item['children'] = $children;
            }            
        }
    }

    return $pictures;

}

But still i can't figure how to get the data as :

8->7->6->5->4->3->2->1->0

or

a[0]{
   'member_id' => 8,
   'user_id' => 7
},
a[1]{
   'member_id' => 7,
   'user_id' => 6
},

I am looking for the best approach to find all the top level parents for a specific child id in a chain of data using PHP MySQL?

Answer 1

Hierarchical data can be tricky, especially if you can't guarantee that it's, say, never more than 2 levels deep or something like that.

This previous answer might be of help: https://stackoverflow.com/a/990536/7595840

You'll find this some in Nested Sets from the link above, but I've had some luck restructuring my data model with more complex hierarchies using a Modified Preorder Tree Traversal Algorithm. It does require restructuring your data a bit, but it can be very helpful with situations like yours in building out full representations of hierarchical trees and be very performant.

Answer 2

You'll want to minimize the number of passes you do, by doing a recursive function you are potentially setting yourself up for a serious problem of performance later. By doing a single pass and uses references you can have this run real fast and work very nicely. The memory usage will also be slightly higher than the original dataset since everything is done by reference and not by copy. If you update one of the records then all the records update with it.

input array

$rows = [
    [ 'id' => 1, 'parent' => null ],
    [ 'id' => 2, 'parent' => 1 ],
    [ 'id' => 3, 'parent' => 1 ],
    [ 'id' => 4, 'parent' => 2 ],
    [ 'id' => 5, 'parent' => 3 ],
    [ 'id' => 6, 'parent' => 4 ],
    [ 'id' => 7, 'parent' => 5 ],
    [ 'id' => 8, 'parent' => 6 ],
    [ 'id' => 9, 'parent' => 7 ],
    [ 'id' => 10, 'parent' => 8 ],
];

variable where you'll store your references

$tree = [];

loop the record set

foreach($rows as $row) {

checking here to see if you've added this row, in theory this should always come back true unless you have duplicate entries

    if (
        false === array_key_exists($row['id'], $tree) ||
        false === array_key_exists('data', $tree[$row['id']])

    ) {
        $tree[$row['id']]['data'] = $row;
    }

checking to see if you have a parent, and then if the parent has been added yet and/or if it's children has been initialized

    if (
        $row['parent'] &&
        (
            false === array_key_exists($row['parent'], $tree) ||
            false === array_key_exists('children', $tree[$row['parent']])
        )
    ) {
        $tree[$row['parent']]['children'] = [];
    }

add a reference of the child onto the parent, take extra care to note the & which says it's by reference

    if ($row['parent']) {
        $tree[$row['parent']]['children'][] = &$tree[$row['id']];
    }
}

$tree becomes the following

[
  1 =>
  [
    'data' =>
    [
      'id' => 1,
      'parent' => NULL,
    ],
    'children' =>
    [
      0 =>
      [
        'data' =>
        [
          'id' => 2,
          'parent' => 1,
        ],
        'children' =>
        [
          0 =>
          [
            'data' =>
            [
              'id' => 4,
              'parent' => 2,
            ],
            'children' =>
            [
              0 =>
              [
                'data' =>
                [
                  'id' => 6,
                  'parent' => 4,
                ],
                'children' =>
                [
                  0 =>
                  [
                    'data' =>
                    [
                      'id' => 8,
                      'parent' => 6,
                    ],
                    'children' =>
                    [
                      0 =>
                      [
                        'data' =>
                        [
                          'id' => 10,
                          'parent' => 8,
                        ],
                      ],
                    ],
                  ],
                ],
              ],
            ],
          ],
        ],
      ],
      1 =>
      [
        'data' =>
        [
          'id' => 3,
          'parent' => 1,
        ],
        'children' =>
        [
          0 =>
          [
            'data' =>
            [
              'id' => 5,
              'parent' => 3,
            ],
            'children' =>
            [
              0 =>
              [
                'data' =>
                [
                  'id' => 7,
                  'parent' => 5,
                ],
                'children' =>
                [
                  0 =>
                  [
                    'data' =>
                    [
                      'id' => 9,
                      'parent' => 7,
                    ],
                  ],
                ],
              ],
            ],
          ],
        ],
        'name' => 'test',
      ],
    ],
  ],
  2 =>
  [
    'data' =>
    [
      'id' => 2,
      'parent' => 1,
    ],
    'children' =>
    [
      0 =>
      [
        'data' =>
        [
          'id' => 4,
          'parent' => 2,
        ],
        'children' =>
        [
          0 =>
          [
            'data' =>
            [
              'id' => 6,
              'parent' => 4,
            ],
            'children' =>
            [
              0 =>
              [
                'data' =>
                [
                  'id' => 8,
                  'parent' => 6,
                ],
                'children' =>
                [
                  0 =>
                  [
                    'data' =>
                    [
                      'id' => 10,
                      'parent' => 8,
                    ],
                  ],
                ],
              ],
            ],
          ],
        ],
      ],
    ],
  ],
  3 =>
  [
    'data' =>
    [
      'id' => 3,
      'parent' => 1,
    ],
    'children' =>
    [
      0 =>
      [
        'data' =>
        [
          'id' => 5,
          'parent' => 3,
        ],
        'children' =>
        [
          0 =>
          [
            'data' =>
            [
              'id' => 7,
              'parent' => 5,
            ],
            'children' =>
            [
              0 =>
              [
                'data' =>
                [
                  'id' => 9,
                  'parent' => 7,
                ],
              ],
            ],
          ],
        ],
      ],
    ],
    'name' => 'test',
  ],
  4 =>
  [
    'data' =>
    [
      'id' => 4,
      'parent' => 2,
    ],
    'children' =>
    [
      0 =>
      [
        'data' =>
        [
          'id' => 6,
          'parent' => 4,
        ],
        'children' =>
        [
          0 =>
          [
            'data' =>
            [
              'id' => 8,
              'parent' => 6,
            ],
            'children' =>
            [
              0 =>
              [
                'data' =>
                [
                  'id' => 10,
                  'parent' => 8,
                ],
              ],
            ],
          ],
        ],
      ],
    ],
  ],
  5 =>
  [
    'data' =>
    [
      'id' => 5,
      'parent' => 3,
    ],
    'children' =>
    [
      0 =>
      [
        'data' =>
        [
          'id' => 7,
          'parent' => 5,
        ],
        'children' =>
        [
          0 =>
          [
            'data' =>
            [
              'id' => 9,
              'parent' => 7,
            ],
          ],
        ],
      ],
    ],
  ],
  6 =>
  [
    'data' =>
    [
      'id' => 6,
      'parent' => 4,
    ],
    'children' =>
    [
      0 =>
      [
        'data' =>
        [
          'id' => 8,
          'parent' => 6,
        ],
        'children' =>
        [
          0 =>
          [
            'data' =>
            [
              'id' => 10,
              'parent' => 8,
            ],
          ],
        ],
      ],
    ],
  ],
  7 =>
  [
    'data' =>
    [
      'id' => 7,
      'parent' => 5,
    ],
    'children' =>
    [
      0 =>
      [
        'data' =>
        [
          'id' => 9,
          'parent' => 7,
        ],
      ],
    ],
  ],
  8 =>
  [
    'data' =>
    [
      'id' => 8,
      'parent' => 6,
    ],
    'children' =>
    [
      0 =>
      [
        'data' =>
        [
          'id' => 10,
          'parent' => 8,
        ],
      ],
    ],
  ],
  9 =>
  [
    'data' =>
    [
      'id' => 9,
      'parent' => 7,
    ],
  ],
  10 =>
  [
    'data' =>
    [
      'id' => 10,
      'parent' => 8,
    ],
  ],
]