CODEWITHSUNDEEP
phparraysmultidimensional-array
user2604754
user2604754

Reputation: 55

Flat Array into tree structure issue

I have following array:

Array
(
    [1] => 0
    [2] => 1
    [3] => 2
    [4] => 3
    [5] => 1
    [6] => 0
)

keys of this array is unique, and values showing parent of key. like parent of 1 & 6 is 0, parent of 2 is 1, for 3 is 2....

I was writing a recursive function which will find the parents for given child id. (4->3->2->1->0) here is my code: but it returns no results

$child_node = 4;

function find_parents($child_node){
    global $tree, $mark;

    $mark[$child_node] = TRUE;

    $ans = array(); //blank array for result

    foreach($tree[$child_node]->children as $child)

        if(!$mark[$child]){
            $ans[$child]=$child;
            find_parents($ans[$child],$child);
        }
     }

Heres is How I create the tree 

class node {

    var $children;
    var $parents;

    public function __construct(){
        $this->children = array();
        $this->parents = array();
    }

}

$tree = array();

foreach ($a as $q => $p){

    if(!isset($tree[$p]))
        $tree[$p] = new node;
    if(!isset($tree[$q]))
        $tree[$q] = new node;

    $mark[$p]=FALSE;
    $mark[$q]=FALSE;
    array_push($tree[$p]->children,$q);

}

Upvotes: 0

Views: 171

Answers (1)

jcsanyi
jcsanyi

Reputation: 8174

You actually don't need a recursive function for this. A simple loop should be enough:

Something like this:

function find_parents($child, $tree) {
    $parents = array();
    while (isset($tree[$child])) {
        $child = $tree[$child]; // move to the immediate parent
        $parents[] = $child;    // and add that parent to the list
    }
    return $parents;
}

You can then call it like this:

$tree = array(1 => 0, 2 => 1, 3 => 2, 4 => 3, 5 => 1, 6 => 0);
find_parents(4, $tree);   // returns array(3, 2, 1, 0)
find_parents(5, $tree);   // returns array(1, 0)

If you want to include the child in the returned list, you can just add it to the line at the beginning of the function, like this:

$parents = array($child);

Upvotes: 1

Related Questions