How to construct binary tree sorting

how to sort and output one-dimensional arrays by building a binary tree

I have built a binary tree, but the result of solving the binary tree is not what I want. What I want is an ordered one-dimensional array:

data

$nodes = array(8,3,10,1,6,14,4,7,13);

Code for building a binary tree

function insertNode($node,$newNode){

    //var_dump($node);
    //var_dump($newNode);
    //exit;
    if ($node["key"] < $newNode["key"]){

        if (empty($node["right"])){
            $node["right"] = $newNode;
        }else{
            $node["right"] = insertNode($node["right"],$newNode);
        }
    }elseif ($node["key"] > $newNode["key"]){

        if (empty($node["left"])){
            $node["left"] = $newNode;
        }else{
            $node["left"] = insertNode($node["left"],$newNode);
        }
    }

    return $node;
}

function tree($nodes)
{
    $node = [
        "key" => "",
        "left" => "",
        "right" => ""
    ];
    $newNode = [
        "key" => "",
        "left" => "",
        "right"=> ""
    ];

    foreach ($nodes as $key => $value){
        //insert($value,$key);
        if($key == 0)
        {
            $node["key"] = $value;  
            continue;
        }
        
        $newNode["key"] = $value;
        //
        $node = insertNode($node,$newNode);
    
    }

    //
    $node = midSortNode($node);

    return $node;
}


var_dump(tree($nodes));

the following is the binary tree constructed

array (size=3)
  "key" => int 8
  "left" => 
    array (size=3)
      "key" => int 3
      "left" => 
        array (size=3)
          "key" => int 1
          "left" => string "" (length=0)
          "right" => string "" (length=0)
      "right" => 
        array (size=3)
          "key" => int 6
          "left" => 
            array (size=3)
              ...
          "right" => 
            array (size=3)
              ...
  "right" => 
    array (size=3)
      "key" => int 10
      "left" => string "" (length=0)
      "right" => 
        array (size=3)
          "key" => int 14
          "left" => 
            array (size=3)
              ...
          "right" => string "" (length=0)

the following is the code for solving the binary tree

function midSortNode($node){
    $sortArr = [];
    if (!empty($node)){
        $sortArr[] = midSortNode($node["left"]);
        //$sortArr["left"] = midSortNode($node["left"]);
        
        array_push($sortArr,$node["key"]);

        $sortArr[] = midSortNode($node["right"]);
        //$sortArr["right"] = midSortNode($node["right"]);
    }

    return $sortArr;
}

var_dump(midSortNode($node));

The result of the

solution is as follows. It seems to be in order, but it is not an one-dimensional array

  0 => 
    array (size=3)
      0 => 
        array (size=3)
          0 => 
            array (size=0)
              ...
          1 => int 1
          2 => 
            array (size=0)
              ...
      1 => int 3
      2 => 
        array (size=3)
          0 => 
            array (size=3)
              ...
          1 => int 6
          2 => 
            array (size=3)
              ...
  1 => int 8
  2 => 
    array (size=3)
      0 => 
        array (size=0)
          empty
      1 => int 10
      2 => 
        array (size=3)
          0 => 
            array (size=3)
              ...
          1 => int 14
          2 => 
            array (size=0)
              ...

how to solve the binary tree into the following one-dimensional array

array (size=9)
  0 => int 1
  1 => int 3
  2 => int 4
  3 => int 6
  4 => int 7
  5 => int 8
  6 => int 10
  7 => int 13
  8 => int 14

Php

May.28,2022