get parent nodes from a node tree array

Question

[
  {
    "id": 1573695284631,
    "name": "Cars",
    "pid": 0,
    "children": [
      {
        "id": 1573695292010,
        "name": "Audi",
        "pid": 1573695284631
      },
      {
        "id": 1573695305619,
        "name": "BMW",
        "pid": 1573695284631,
        "children": [
          {
            "id": 1573695328137,
            "name": "3 Series",
            "pid": 1573695305619
          },
          {
            "id": 1573695335102,
            "name": "X5",
            "pid": 1573695305619
          }
        ]
      }
    ]
  },
  {
    "id": 1573695348647,
    "name": "Motorcycles",
    "pid": 0,
    "children": [
      {
        "id": 1573695355619,
        "name": "Ducatti",
        "pid": 1573695348647
      }
    ]
  }
]

Suppose I have this node-tree-like array in PHP (represented above in json for readability). For a given child node ID, I would like to find all parent node IDs that it's nested under. For example,

getParentNodes($haystack, $child_node_id=1573695328137); //[1573695284631, 1573695292010, 1573695305619]

I assume this is a use case for recursion. Here's my best attempt:

function getParentNodes($haystack, $child_node_id) {

    if( empty($haystack->children) )
        return;

    foreach($haystack->children as $child) {
        if($child->id == $child_node_id) {
            // $child found, now recursively get parents
        } else {
            getParentNodes($child, $child_node_id);
        }
    }
}

Answer 1

This one will walk the tree until it hits the desired id. In all cases where the leaf is not the desired one, it will return false - and collapse up the stack resulting in false or an array of parent-ids if the child is found.

Code

function getParentNodes($haystack, $child_node_id) {
    foreach ($haystack as $element) {
        if ($element['id'] === $child_node_id) {
            // return [$element['id']]; // uncomment if you want to include child itself
            return [];
        } else if (array_key_exists('children', $element)) {
            $parentNodes = getParentNodes($element['children'], $child_node_id);
            
            if ($parentNodes !== false) {
                return [$element['id'], ...$parentNodes];
            }
        }
    }
    
    return false;
}

Outputs parent ids:

array(2) {
  [0]=>
  int(1573695284631)
  [1]=>
  int(1573695305619)
}

Working example.

Answer 2

You missing return result. This is what you want.

function getParentNodes($arr, $child_node_id) {

    $result = [];

    foreach($arr as $item) {

        if($item->pid == $child_node_id) {
            $result[] = $item->id;
        }

        if(!empty($item->children)) {
            $result[] = getParentNodes($item->children, $child_node_id);
        }

    }

    return $result;
}

also you need get values as flat array

$values = getParentNodes($values, 1573695284631);

// do flat arr
array_walk_recursive($values,function($v) use (&$result){ $result[] = $v; });

// your values
var_dump($result);

Source reference for flat array

Answer 3

I ended up writing 2 recursive functions

function treeSearch($needle, $haystack) {
    foreach($haystack as $node) {
        if($node->id == $needle) {
            return $node;
        } elseif ( isset($node->children) ) {
            $result = treeSearch($needle, $node->children);
            if ($result !== false){
                return $result;
            }
        }
    }

    return false;
}

treeSearch will find the node in the tree, then I need to recursively go up the tree until the parent id (pid) is 0

function getParents($node, $hierarchy, $all_parent_ids=[]) {
    if($node->pid != 0) {
        $parent_node = treeSearch($node->pid, $hierarchy);
        $all_parent_ids[] = $parent_node->id;
        $result = getParents($parent_node, $hierarchy, $all_parent_ids);

        if ($result !== false){
            return $result;
        }
    }

    return $all_parent_ids;
}

then, supposing the tree is called $tree I can call them like:

$node = treeSearch(1573695328137, $tree);
$parents = getParents($node, $tree);

Answer 4

This is the best solution to take the parent of a child !

function getPathParent($id, $tree='',$opts='', &$path = array()) {
    $in = array_replace(array(
        'id'=>'id',
        'child'=>'children',
        'return'=>'id'
    ),(array)$opts);
    if ( is_array($tree) && !empty($tree) ){
        foreach ($tree as $item) {
            if ($item[$in['id']] == $id) {           
                array_push($path, $item[$in['return']]);
                return $path;
            }
            if ( isset($item[$in['child']]) && !empty($item[$in['child']]) ) {
                array_push($path, $item[$in['return']]);
                if (getPathParent($id, $item[$in['child']],$opts, $path) === false) {
                    array_pop($path);
                } else {
                    return $path;
                }
            }
        }
    }
    return false;
}


$tree = [
    [
        "id" => 1573695284631,
        "name" => "Cars",
        "pid" => 0,
        "children" => [
            [
                "id" => 1573695292010,
                "name" => "Audi",
                "pid" => 1573695284631
            ],
            [
                "id" => 1573695305619,
                "name" => "BMW",
                "pid" => 1573695284631,
                "children" => [
                    [
                        "id" => 1573695328137,
                        "name" => "3 Series",
                        "pid" => 1573695305619
                    ],
                    [
                        "id" => 1573695335102,
                        "name" => "X5",
                        "pid" => 1573695305619
                    ]
                ]
            ]
        ]
    ],
    [
        "id" => 1573695348647,
        "name" => "Motorcycles",
        "pid" => 0,
        "children" => [
            [
                "id" => 1573695355619,
                "name" => "Ducatti",
                "pid" => 1573695348647
            ]
        ]
    ]
];


$getParentNode = getPathParent(1573695335102,$tree);
var_export($getParentNode);
// return: 
/*
array (
  0 => 1573695284631,
  1 => 1573695305619,
  2 => 1573695335102,
)
*/
$getParentNode = getPathParent(1573695335102,$tree,array('return'=>'name'));
var_export($getParentNode);
// return: 
/*
array (
  0 => 'Cars',
  1 => 'BMW',
  2 => 'X5',
)
*/
$getParentNode = getPathParent(1573695335102,$tree,array('id'=>'id','child'=>'children','return'=>'pid'));
var_export($getParentNode);
// return: 
/*
array (
  0 => 0,
  1 => 1573695284631,
  2 => 1573695305619,
)
*/