Binary Tree Implementation in PHP

Photo by veeterzy on Unsplash

A data structure is a way of organizing data in some way so that it can be used effectively. This includes, but is not limited to making it easy to access and update the data. The concept of data structures is one that every programmer should aim to be conversant with.

There a number of data structures but I will only focus on the binary tree. I will show a simple way to implement a binary tree in PHP.

I will just highlight a few properties of the binary tree before diving into its implementation in PHP. However, if you would like to know more about binary trees check out some free tutorials online on data structures.

A binary tree is a data structure where each node in a tree has at most two children. Binary trees are most commonly applied in search applications.

Characteristics of binary trees.

1. A binary tree is made up of nodes with each node containing a left and right reference and a data element. In our example above the left reference for node 10 is 6, the right reference is 18 and the data element which is the value of the node is 10.
2. The topmost node is called the root node. In the above example, the root would be10.
3. The nodes connected to a single node are referred to as it’s children and that node is referred to as their parent node. Two nodes with the same parent are referred to as siblings. In our example taking 10, it’s child nodes are 6 and 18. Relatedly 6 and 18 are siblings.
4. Nodes in a binary tree are placed according to this rule: the value of a node is greater than or equal to the values of any descendant in its left branch, and less than the value of any descendant in its right branch. This is the Binary Search Tree Invariant (BST).
5. In our example, nodes 4,8,15 and 21 are the outer nodes and it is to these nodes that new nodes would be added. They are all called leaf nodes because they don’t have any child nodes.

We will be following these properties when implementing the binary tree in PHP.

First, we build the BinaryNode class which constructs every node.

<?php
/**
* This is a class for creating the binary nodes
*/
class BinaryNode {
public $data;
public $left;
public $right;
public function __construct(string $data = NULL) {
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
/**
* Adds child nodes
*/
public function addChildren($left, $right) {
$this->left = $left;
$this->right = $right;
}
}

We declare three private variables ie $data, $left and $right. The data stores the value of the node, left and right will hold the left and right references for the node.

The addChildren method will allow us to add child nodes to any node.

Next, we build the BinaryTree class.

/**
* Class for creating the binary tree
*/
class BinaryTree {
private $root = null;
public function __construct() {
$this->root = null;
}

We declare a private variable $root which will be the root of the binary tree.

Inserting elements to the binary tree

/**
* Method to check if the tree is empty
*/
public function isEmpty() {
return $this->root === null;
}
/**
* Method to insert elements in to the binary tree
*/
public function insert($data) {
$node = new BinaryNode($data);
if ($this->isEmpty()) { // this is the root node
$this->root = $node;
return true;
} else {
return $this->insertNode($node, $this->root);
}
}
/**
* Method to recursively add nodes to the binary tree
*/
private function insertNode($node, $current) {
$added = false;
while($added === false) {
if ($node->data < $current->data) {
if($current->left === null) {
$current->addChildren($node, $current->right);
$added = $node;
break;
} else {
$current = $current->left;
return $this->insertNode($node, $current);
}
}
elseif ($node->data > $current->data) {
if($current->right === null) {
$current->addChildren($current->left, $node);
$added = $node;
break;
} else {
$current = $current->right;
return $this->insertNode($node, $current);
}
} else {
break;
}
}
return $added;
}

To add elements to the binary we need to make sure that we satisfy all the properties of the binary tree above.

We need to first check if the binary tree is empty. If it is then the node to be added is the root. If not then we add the node keeping in mind the binary tree properties.

We use the insertNode method recursively to insert the node at the correct position. We need to traverse the binary tree until we get to the correct position to add the node.

Retrieve node from the binary tree

/**
* Method to retrieve a node from the binary tree
*/
public function retrieve($node) {
if ($this->isEmpty()) {
return false;
}
$current = $this->root;
if ($node->data === $this->root->data) {
return true;
} else {
return $this->retrieveNode($node, $current);
}
}
/**
* Method to recursively add nodes to a binary tree
*/
private function retrieveNode($node, $current) {
$exists = false;
while($exists === false) {
if ($node->data < $current->data) {
if ($current->left === null) {
break;
}
elseif($node->data == $current->left->data) {
$exists = $current->left;
break;
}
else {
$current = $current->left;
return $this->retrieveNode($node, $current);
}
}
elseif ($node->data > $current->data) {
if ($current->right === null) {
break;
}
elseif($node->data == $current->right->data) {
$exists = $current->right;
break;
} else {
$current = $current->right;
return $this->retrieveNode($node, $current);
}
}
}
return $exists;
}

To retrieve a node we need to traverse the binary tree until we either get to that node or we hit a leaf node in which case we would know the node is not in the binary tree.

For example, if we had to retrieve 21 from the example above. Following the binary tree properties, 21 being greater than the root means we need to traverse the right subtree. We move on to node 18, 21 being greater than 18 again means we move on to this nodes’ right subtree as well. So keep going until we either hit a leaf node, in which case the element doesn’t exist in the binary tree or as is the case in this example, we get to the element we are looking for.

Removing nodes

There are four cases that may arise in removing a node from a binary tree:

• Removing the root node
• Removing a leaf node
• Removing a node with either a right or left subtree but not both
• Finally, removing a node with both right and left subtrees

I will only explain the first two cases, however, I will add the last two cases to my repo.

Removing a root node

The idea here is that we need to find a replacement for the root node before we can remove it. However, the replacement has to satisfy the BST invariant. We can achieve this in two ways ie:

• Find the smallest node in the right subtree
• Find the biggest node in the left subtree

I chose to go with the second way but either way is fine.

/**
* Method to remove an element from the binary tree
*/
public function removeElement($elem) {
if ($this->isEmpty()) {
return false;
}
$node = $this->retrieve($elem);
if (!$node) {
return false;
}
if ($elem->data === $this->root->data) {
// find the largest value in the left sub tree
$current = $this->root->left;
while($current->right != null) {
$current = $current->right;
continue;
}
// set this node to be the root
$current->left = $this->root->left;
$current->right = $this->root->right;
//Find the parent for the node and set it as the parent for any //children the node may have had
$parent = $this->findParent($current, $this->root);
$parent->right = $current->left;
//finally set that node as the new root for the binary tree
$this->root = $current;
return true;
}

We can see in the snippet above, that I find the largest node in the left subtree and set it to be the root.

Removing a leaf node

/**
* Method to remove an element from the binary tree
*/
public function removeElement($elem) {
if ($this->isEmpty()) {
return false;
}
$node = $this->retrieve($elem);
if (!$node) {
return false;
}
// case two we are removing a leaf node
if ($node->left === null and $node->right === null) {
$parent = $this->findParent($node, $this->root);
if ($parent->left->data && $node->data === $parent->left->data) {
$parent->left = null;
return true;
}
elseif ($parent->right->data && $node->data === $parent->right->data) {
$parent->right = null;
return true;
}
}

In this case, all I need to do is find the parent node using the findParent method for the leaf node and set it’s either right or left reference to null depending on where the leaf node was.

private function findParent($child, $current) {
$parent = false;
while ($parent === false) {
if ($child->data < $current->data) {
if ($child->data === $current->left->data) {
$parent = $current;
break;
} else {
return $this->findParent($child, $current->left);
break;
}
}
elseif ($child->data > $current->data) {
if ($child->data === $current->right->data) {
$parent = $current;
break;
} else {
return $this->findParent($child, $current->right);
break;
}
} else {
break;
}
}
return $parent;
}

The code for this binary tree implementation can be found here. I will be adding more methods to enable node removal, tree traversal and also printing the tree.

Any questions please do add in the comments and I will respond. Suggestions are also very welcome.

Thank you