Как изменить логику вставки этого узла дерева, чтобы получить сбалансированное двоичное дерево?

Я новичок в кодировании для деревьев.

Учитывая следующий входной массив —

array(10,7,13,5,6,8,11,15,14,4,3,16)

Я хотел бы подготовить сбалансированное двоичное дерево, вставляя эти значения одно за другим, начиная с первого элемента (должен быть вставлен левый потомок узла, затем правый потомок, затем следующий узел, чтобы вставить его левый и правый потомки Все вставки должны происходить сначала до уровня, а затем до более высокого уровня). Результат должен выглядеть так —

Вот код, который я сейчас имею (немного измененный из кода BST, который я нашел Вот)

<?phpclass Node
{

public $left;
public $right;
public $data;

public function __construct($data)
{
$this->data = $data;
$this->right = NULL;
$this->left = NULL;
}

} //End class Node

class BTree
{

public $root;

public function __construct()
{
$this->root = NULL;
}

/* Insert the first node to the BST*/
public function insert($data)
{

$node = new Node($data);

if($this->root === NULL)
$this->root = $node;
else
$this->insertNode($this->root,$node);

}

/* Insert node starting from root */
public function insertNode(&$root,$node)
{
if($root === NULL)
{//root is not occupied, set root as the node
$root = $node;
}
else
{
if($root->left && $root->left->data===null)
{
$root->left==$node;
}
else
{
if($root->right && $root->right->data===null) //Not using else to avoid duplicate values
{
$root->right==$node;
}
else
{
$this->insertNode($root->left,$node); //Search for place in the right side to insert
}
}
}
}

/* Get an array and insert all items in it to the tree in the array order */
public function multiInsert($array)
{

foreach($array as $data)
$this->insert($data);
}/*
Draw the tree from left to right
Line with same color are in same level of the tree
*/
public function draw($node = 'root', $depth = 0)
{

if($node == 'root') $node = $this->root; /* If node not selected the default is the tree root */

if ($node === null) return;

return
$this->draw($node->right, $depth + 1).str_repeat("&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;", $depth).
"<span style='color:".(($depth%2 == 0)? 'red' : 'blue')."'>".$node->data."</span><br>".
$this->draw($node->left, $depth + 1);
}

} //End class BTree/* ########### EXAMPLE ########### */
echo '<h1>Binary Tree</h1>';
$tree = new BTree();
$tree->multiInsert(array(10,7,13,5,6,8,11,15,14,4,3,16));
echo'<br><br>';
echo $tree->draw();

?>

В результате получается дерево с только левыми дочерними элементами, как показано в следующем выводе: