5

I want to create a PHP recursive program using a Binary Tree and Recursion.

I want to print the binary tree level by level using recursion. I want to recurse through the tree, push the node into a hashmap that has the level as the reference point.

Here's what I have so far:

$binary_tree = array(array(1 => array(2 => array(4,5),4=>array(5,6))));

            1
            |
    ------------------
    |                |
    2                4
    |                |
----------        ----------
|        |        |        |
4        5        5        6

And the end result should look like this:

$data[0] = array(1);  
$data[1] = array(2,4);  
$data[2] = array(4,5,5,6);  

I can easily loop through the array and print out the numbers, which are corresponding to the level(the array index).

Here's the function, which is wrong, but my first shot:

function recurse_tree($data,$level=0){
    $final = array();
    $tmp = array()
    // first check if data is array
    if(is_array($data)){
        // loop through data 
        foreach($data as $elm){
            // push data to the tmp array
            $tmp[] = recurse_tree($elm,$level+1);
        }
        // not an array
    } else {
            // push data to the final array. can we push to the tmp array.
            array_push($final[level],$elm);
    }
    // merge final and tmp array and return
    return ($final + $tmp);
 }

I am not too experienced with recursion nor problem solving, so I wrote out the steps below which are occurring. The problem I have here now is that on step 9 I an unsure how to handle the keys 2 and 4, and then finally to handle the root node, key 1. Also, when I get to steps 5-8, im at level 4, which is correct, however according to the tree, its level 2.

$flattened_tree = recurse_tree($data);

// STEPS:  
1./ called recurse_tree  
    data: array(array(1 => array(2 => array(4,5),4=>array(5,6))));  
    level: 0  
    final:  array();  
    tmp:  array();  
2./ called recurse_tree:  
    data: array(1 => array(2 => array(4,5),4=>array(5,6)));  
    level: 1  
    final: array();  
    tmp: array();  
3./ called recurse_tree:  
    data: array(2 => array(4,5),4=>array(5,6));  
    level: 2
    final: array();  
    tmp: array();
4./ called recurse_tree:
    data: array(4,5)
    level: 3
    final: array();  
    tmp: array();
5./ called recurse_tree:
    data: 4
    level: 4
    final: array(4 => 4)
    tmp: array()
6./ called recurse_tree:
    data: 5
    level: 4
    final: array(4 => 5)
    tmp: array(4 => 4)
7./ called recurse_tree:
    data: 5
    level: 4
    final: array(4=> 5)
    tmp: array(4 => array(4,5))
8./ called recurse_tree:
    data: 6
    level: 4
    final: array(4 => 6)
    tmp: array(4 => array(4,5,5))         

What is the best way to implement a Binary Tree recursion algorithm?

2 Answers 2

11

If I understand correctly, this is what you want:

function tree(array $data, &$tree = array(), $level = 0) {
    // init
    if (!isset($tree[$level])) $tree[$level] = array();

    foreach ($data as $key => $value) {
        // if value is an array, push the key and recurse through the array
        if (is_array($value)) {
            $tree[$level][] = $key;
            tree($value, $tree, $level+1);
        }

        // otherwise, push the value
        else {
            $tree[$level][] = $value;
        }
    }
}

Use it like this:

$binary_tree = array(1 => array(2 => array(4,5),4=>array(5,6)));
tree($binary_tree, $output);
var_dump($output);

This gives you:

array(3) {
  [0]=>
  array(1) {
    [0]=>
    int(1)
  }
  [1]=>
  array(2) {
    [0]=>
    int(2)
    [1]=>
    int(4)
  }
  [2]=>
  array(4) {
    [0]=>
    int(4)
    [1]=>
    int(5)
    [2]=>
    int(5)
    [3]=>
    int(6)
  }
}
1
  • 1
    By the way, what would be the time complexity of this solution. Just curious! Commented Jul 21, 2016 at 19:51
2

This function in class Tree view

you have got a return of array which has all node value then you can arrange on below tree view .

function getTreeDataFromReg($setid)
{
    if(!empty($setid))
    {
        for($in=0 ;$in<7;$in++ )
        {
            if($setid[$in]>0)
            {
                $result=$this->selectQuery(
                    "tbl_registration"," * "," fl_reg_id ='".$setid[$in]."'",
                    " fl_placment_side ASC ");
                $setar=mysql_fetch_array($result);
                $leftid=$setar['fl_left_id'];
                $rightid=$setar['fl_right_id'];
            }else
            {
                $leftid=0;
                $rightid=0;
            }
            switch($in)
            {
                case 0: $setid[1]=$leftid;
                        $setid[2]=$rightid;
                        break;
                case 1: $setid[3]=$leftid;
                        $setid[4]=$rightid;
                        break;      
                case 2: $setid[5]=$leftid;
                        $setid[6]=$rightid;
                        break;
                case 3: $setid[7]=$leftid;
                        $setid[8]=$rightid;
                        break;  
                case 4: $setid[9]=$leftid;
                        $setid[10]=$rightid;
                        break;
                case 5: $setid[11]=$leftid;
                        $setid[12]=$rightid;
                        break;  
                case 6: $setid[13]=$leftid;
                        $setid[14]=$rightid;
                        break;                                                      
            }
        }  
    }   
    return $setid;
}   
function printTreeView($parentid)
{
    $setid=array($parentid);
    $setarra=$this->getTreeDataFromReg($setid);
    return $setarra;
}

Which creates a binary tree:

            0
         /     \
        1        2
       / \      / \
      3   4    5   6
     /\  / \  /\   /\

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.