Creating a binary tree using a PHP array

We can implement a binary tree using a PHP array. Since a binary tree has a maximum of zero to two child nodes, we can use the maximum child nodes as 2 and construct a formula to find the child nodes of a given node. Let's number the nodes in a binary tree from top to bottom and left to right. So, the root node will have number 0, the left child 1, and right child 2, and this will follow until each node is numbered, just like the following diagram:

We can easily see that for node 0, the left child is 1, and the right child 2. For node 1, the left child is 3, and the right child is 4, and it goes on. We can easily put this in a formula:

If i is our node number, then:

Left node = 2 X i + 1

Right node = 2 X (i + 1)

Let's now create our example for the match schedule part using a PHP array. If we rank it as per our discussion, then it will look like this:

    $nodes = []; 
    $nodes[] = "Final"; 
    $nodes[] = "Semi Final 1"; 
    $nodes[] = "Semi Final 2"; 
    $nodes[] = "Quarter Final 1"; 
    $nodes[] = "Quarter Final 2"; 
    $nodes[] = "Quarter Final 3"; 
    $nodes[] = "Quarter Final 4";

Basically, we will create an array with auto-indexing, starting from 0. This array will be used as a binary tree representation. Now, we will modify our BinaryTree class to use this array instead of our node class, with left and right child nodes as well as the traversal method. Now, we will traverse based on the node number instead of the actual node reference:

class BinaryTree { 

    public $nodes = []; 

    public function __construct(Array $nodes) { 
      $this->nodes = $nodes; 
    } 

    public function traverse(int $num = 0, int $level = 0) { 

      if (isset($this->nodes[$num])) { 
          echo str_repeat("-", $level); 
          echo $this->nodes[$num] . "
"; 

          $this->traverse(2 * $num + 1, $level+1); 
          $this->traverse(2 * ($num + 1), $level+1); 
      } 
    } 

}

As we can see from preceding implementation, the traverse part uses the node positioning instead of a reference. This node position is nothing but the array indexes. So, we can directly access the array index and check whether it's empty or not. If not, we can continue to go deeper using the recursive way. If we want to create the binary tree using the array and print the array values, we have to write the following code:

$tree = new BinaryTree($nodes); 
$tree->traverse(0);

If we run this code in the command line, we will see following output:

Final
-Semi Final 1
--Quarter Final 1
--Quarter Final 2
-Semi Final 2
--Quarter Final 3
--Quarter Final 4

We can use a simple while loop to iterate through the array and visit each node instead of proceeding recursively. In all our recursive examples, we will see that some are more efficient if we use them the iterative way. We can also just use them directly instead of creating a class for the binary tree.

Table of Contents for Creating a binary tree using a PHP array

Create new playlist

Sign In

Sign Up

Table of Contents for
Creating a binary tree using a PHP array