Why does the algorithm select this cell and not another?

Question

PHP

$tree = R::findOne('users', 'id = 1');
$parentid = 0;
function check_node($x){
    global $parentid;
    global $choosenbranch;
        $right = R::findOne('users', 'parentid = ? AND branch = 1', array($x));
        if($right){
            $choosenbranch = 0;
            check_node($right->id);
        }else{
            $parentid = $x;
        }

        $left = R::findOne('users', 'parentid = ? AND branch = 0', array($x));
        if($left){
            $choosenbranch = 1;
            check_node($left->id);
        }else{
            $parentid = $x;
        }
}
check_node($tree->id);
echo $parentid;
echo '<br>';
echo $choosenbranch;

there tree

$parentidshould be equal to 3, because there is free and right and left space (filling from right to left), but he chooses 4, why is that, where is the error in the logic?

Answer 1

Literally recently I came across the need for such a solution.
Here is the most suitable one from my
mortgage