General tree traversal(infinite) in breadth-first

I have a Tree Structure where each node has 5 child nodes and more than that are not allowed. I wish to traverse this tree in breadth-first search manner.

Now I wish to calculate empty node from selected parent using breadth-first search manner.

e.g.

if given parent is 1, then function must return node 4 because it has positions available.
If given parent is 2, then it must return node 7

I am using PHP(codeigniter) + Mysql for this.

My controler

public function addmember()
{
    $current_node = $this->input->post('member');
    $empty_location = $this->tree_model->GetEmptyPositions($current_node);
    if($empty_location != 0) {
        echo "Position available";
    }
    else {
        $next_nodes = $this->tree_model->GetAllChilds($current_node);
        $i=0;
        for($i=0;$i<5;$i++){
            $result = $this->tree_model->GetEmptyPositions($next_nodes[$i]);
            if($result != 0 ) {
                $current_node = $next_nodes[$i];
                goto exe;
            }
        }

    }
    exe:
    echo $current_node;
}

and my model

//get number of empty nodes of current member
public function GetEmptyPositions($id) {
    $this->db->select('empty_position');
    $this->db->from('member');
    $this->db->where('member_id',$id);
    $result = $this->db->get();
    if ($result->num_rows() > 0)
        foreach($result->result() as $empty_pos)
            return $empty_pos->empty_position;
}

//get all childs of current node
public function GetAllChilds($id) {
    $this->db->select('member_id');
    $this->db->from('member');
    $this->db->where('tree_parent_id',$id);
    $result = $this->db->get();
    if ($result->num_rows() > 0) {
        $i = 0;
        foreach($result->result_array() as $member_id) {
            $member_array[$i] = $member_id['member_id'];
            $i++;
        }
        return $member_array;
    }
}

Database

CREATE TABLE IF NOT EXISTS `member` (
   `member_id` int(11) NOT NULL AUTO_INCREMENT,
   `datetime` datetime DEFAULT NULL,
   `parent_id` int(11) DEFAULT NULL,
   `tree_parent_id` int(11) DEFAULT NULL,
   `empty_position` tinyint(4) DEFAULT '5', // stores how many empty positions remain if zero move to next node
   `name` varchar(20) COLLATE utf8_unicode_ci DEFAULT NULL,
    PRIMARY KEY (`member_id`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

Where I stuck up!

I am able to traverse till node 6 by above code. but in next iteration i have need to check @ node 7 since nodes will be in order 5 rase to n and it is not finite tree structure.

next tree traversal order 7 8 9 10 11 12 13 14 16 ......

I am still thinking, but much faster than traversing the tree would be a position_id for every possible position. If you look at a complete tree of a certain level you would see what I mean - your example looks like that.

The connections between position and position_id are something with simple int arithmetic (div and modulo).

All nodes in a subtrees share some of those properties - for example the direct subnodes of node 4 (third node in second row) are numbers

1 + 5 + (3-1)*5 +   1 
1 + 5 + (3-1)*5 +   2
1 + 5 + (3-1)*5 +   3
1 + 5 + (3-1)*5 +   4
1 + 5 + (3-1)*5 +   5

So you still would have to traverse the levels in a loop, but not the nodes if you manage that position number in every node.

Step 2:

Row r has 5^r elements (starting with row 0).

Store in every node the row and the column, in every row the column starts with 0. So the second row is not 2,3,4,5,6 but is 1|0, 1|1, 1|2, 1|3, 1|4.

If your search root is 1|1 (row 1, second element, in your nice tree named "3"), then all children in row 2 have

  col / 5 = 1

all children in row 3 have

  col / 25 = 1

and so on.

One level below node 2|10 are nodes 3|(5*10) til 3|(5*11-1) = 50 .. 55-1

two levels below are nodes 4|(50*5) til 4|(55*5-1)

and so on.

Step 3

Pseudocode:

getFreeNode($node){
    $rowMax = 100;
    $row   = $node->row + 1;
    $from  = 5 * $node->col;
    $to    = $from + 5;
    while($row <= $rowMax){
        if ($id = query("select id from member " 
            ."where row = $row and col >= $from and col < $bis"
            ." and empty_position > 0"))
        {
            return $id;
        }
        $row++;
        $from *= 5;
        $to *= 5;
    }
}

insertNode($parent, $node){
    $node->row = $parent->row + 1;
    $node->col = 5*$parent->col + (5 - $parent->freeNodeCount);
    $node->parent_id = $parent->member_id
}

Please ask if more details are needed.