Flat Array into tree structure issue

Question

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);

}

I'm not entirely clear on what you're trying to do, and your code above is incomplete (missing end of the function, no return, etc.) If you're just trying to get the list of parents from the original array, recursion is not actually needed. See my answer for a solution to that, or please provide more clarification. — jcsanyi
– jcsanyi, Commented Jul 22, 2013 at 0:00

jcsanyi · Accepted Answer · 2013-07-21 23:54:48Z

1

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);

answered Jul 21, 2013 at 23:54

jcsanyi

8,2042 gold badges31 silver badges52 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

user2604754 Over a year ago

I get an object back with the parents array empty

jcsanyi Over a year ago

I'm not sure what you mean - there's no objects at all in this code. Are you mixing it with your original code, perhaps? This function operates directly on the original array, not on any tree object.

user2604754 Over a year ago

yeah I think I am mixing it, how can use with the tree object? I want to later on climb the tree and find nodes

Collectives™ on Stack Overflow

Flat Array into tree structure issue

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related