We will now create a binary tree (not a binary search tree). The key factor to have in a binary tree is that we must have two placeholders for the left child node and the right child node, along with the data we want to store in the node. A simple implementation of a binary node will look like this:

class BinaryNode { 

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

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

    public function addChildren(BinaryNode $left, BinaryNode $right) { 
      $this->left = $left;
      $this->right = $right;
    }

}

The preceding code shows that we have a class with tree properties to store data, left and right. When we are constructing a new node, we are adding the node value to the data property, and left and right is kept NULL as we are not sure if we need those or not. We also have an addChildren method to add left children and right children to a particular node.

Now, we will create a binary tree class where we can define the root node as well as the traversal method similar to our basic tree implementation earlier in this chapter. The difference between two implementations is the traversal process. In our previous example, we used foreach to traverse each child node as we did not know how many nodes are there. Since each node in the binary tree can have a maximum of two nodes and they are named as left and right, we can only traverse the left node and then the right node for each particular node visit. The changed code will look like this:

class BinaryTree { 

    public $root = NULL; 

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

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

      if ($node) { 
          echo str_repeat("-", $level); 
          echo $node->data . "
"; 

          if ($node->left) 
            $this->traverse($node->left, $level + 1); 

          if ($node->right) 
            $this->traverse($node->right, $level + 1); 
         } 
    } 

} 

It looks very similar to the basic tree class we had earlier in this chapter. Now, let's fill up the binary tree with some nodes. Usually, in any football or cricket tournament, we have knockout rounds where two teams play with each other, the winner moves forward, and it continues to the final. We can have a similar structure as a binary tree for our example. So, let's create some binary nodes and structure them in a hierarchy:

$final = new BinaryNode("Final"); 

$tree = new BinaryTree($final); 

$semiFinal1 = new BinaryNode("Semi Final 1"); 
$semiFinal2 = new BinaryNode("Semi Final 2"); 
$quarterFinal1 = new BinaryNode("Quarter Final 1"); 
$quarterFinal2 = new BinaryNode("Quarter Final 2"); 
$quarterFinal3 = new BinaryNode("Quarter Final 3"); 
$quarterFinal4 = new BinaryNode("Quarter Final 4"); 

$semiFinal1->addChildren($quarterFinal1, $quarterFinal2); 
$semiFinal2->addChildren($quarterFinal3, $quarterFinal4); 

$final->addChildren($semiFinal1, $semiFinal2); 

$tree->traverse($tree->root); 

First, we created a node called final and made it as a root node. Then, we created two semifinal nodes and four quarter final nodes. Two semifinal nodes each have two quarter final nodes as left and right child nodes. The final node has two semifinal nodes as left and right child nodes. The addChildren method is doing the children assignment job for the nodes. In the last line, we traversed the tree and displayed the data hierarchically. If we run this code in the command line, we will see the following output:

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