Traversing B-Tree Structure Algorithm

Question

I'm having a hard time trying to write a traversing function that outputs a child-node's parent-nodes.

Take a look at the example b-tree

Here is the sample dataset I'm using:

$nodes = array(
  array('f','b'),
  array('f','g'),
  array('b','a'),
  array('b','d'),
  array('g','i'),
  array('d','c'),
  array('d','e'),
  array('i','h')
);

I'm trying to output a results array that contains all child node arrays which contain parent associations.

Example Outputs:

• node(d)'s parents are (b,f)
• node(c)'s parents are (d,b,f)
• node(h)'s parents are (i,g,f)

I can't figure out how to traverse past the direct parent node.

foreach($nodes as $node){
    //CHECK IF NODE EXISTS
    if(array_key_exists($node[1],$results)){
        //DO NOTHING
        array_push($results[$node[1]],$node[0]);
    }
    else{
        //CREATE NEW CHILD ARRAY
        $results[$node[1]] = [];
        //PUSH PARENT INTO CHILD ARRAY
        array_push($results[$node[1]],$node[0]);
    }
}
foreach($results as $k => $v){
    echo "child[$k] parents(" . implode($v,', ').")" ; 
    echo "</br>";
}

Question: How can I achieve this output in the most efficient manor?

Answer 1

The best way to deal with such cases is to use recursive functions.

echo findParents('h',$nodes);

function findParents($find,$btree){
      $parents;
        foreach($btree as $node){
            if($node[1]===$find){
                $parents .=$find.',';
                return $parents .= findParents($node[0], $btree);
            }
        }
     return $find;
    }

Check the live code here: https://www.tehplayground.com/ElTdtP61DwFT1qIc

The only drawback is that it would return the original node in the return list. But I think you can live with that.

I think the better representation of the tree would be:

$nodes = array(
  'f'=>array('d','g'),
  'b'=>array('a','d'),
  'g'=>array('i'),
  'd'=>array('c','e'),
  'i'=>array('h')
);

But that would need slight modification to the above code.

To get an array as the response:

function findParentsArray($find,$btree){
  $parentsArray = explode(',',findParents($find,$btree));
  array_shift($parentsArray);
  return $parentsArray;
}

It should be possible to have that done directly in findParents() but I don't have time to look into it now.