Binary Tree PHP Implementation

btree.php

<?php
/**
 *  A binary tree implementation in PHP 
 *  
 *  features:
 *      - add node
 *      - delete node
 *      - find node by value
 *      - walk tree
 *      - replace node
 *      - traversable interface
 *      - custom comparison callback
 *      - translate btree to graphviz dot
 *      - translate graphviz dot to png
 * 
 */

class BinaryTree implements IteratorAggregate
{
    protected $size = 0;
    protected $cmpCallback;
    public $root;
    
    public function __construct(BinaryNode $rootNode = null)
    {
        if ($rootNode) {
            $this->root = $rootNode;
        } else {
            $this->root = new BinaryNode($this);
        }
        $this->cmpCallback = function($a, $b) {
            if ($a > $b) {
                return 1;
            } elseif ($b > $a) {
                return -1;
            } else {
                return 0;
            }
        };
    }
 
    public function __get($name)
    {
        if ($name === 'size') {
            return $this->size;
        }
    }
 
    public function add($value)
    {
        $this->root->add($value);
        $this->size++;
    }
    
    public function delete(BinaryNode $node)
    {
        // copy the left and right nodes of this subtree
        $left = $node->left;
        $right = $node->right;
        // if this is the parent node then its right subtree must become the parent
        if ($node->isRoot) {
            $this->root = $right;
            if ($right) {
                $right->parent = null;
            }
        } else {
            // otherwise if the node is a right branch
            if ($node->branch instanceof RightBranch) {
                $node->parent->right = $right;
            } elseif ($node->branch instanceof LeftBranch) {
            // if the node is a left branch
                $node->parent->left = $left;
                $left = $right; // right into left
            }
        }

        // Then run each element in the left subtree back through the add method
        $this->size--;
        $tree = $this;
        $this->walk($left, function($nodeValue) use ($tree) {
            if ($nodeValue !== null) {
                $tree->add($nodeValue);
                $this->size--; // because every node we add back was already accounted for
            }
        });  
    }
 
    public function search($value)
    {
        return $this->find($value, $this->root);
    }
 
    protected function find($value, BinaryNode $node = null)
    {
        if ($node === null) {
            return false; // failed to find value in tree
        }
        $cmp = $this->getCmpCallback();
        $cmp = $cmp($value, $node->value);
        if ($cmp == 0) {
            return $node;
        } elseif ($cmp == 1) {
            return $this->find($value, $node->right);
        } elseif ($cmp == -1) {
            return $this->find($value, $node->left);
        }
    }
 
    public function walk(BinaryNode $node = null, Callable $callback = null)
    {
        if (!$callback) { $callback = function($v) { return $v; }; }
        if ($node && $node->value !== null) {
            $resultA = $this->walk($node->left);
            $resultB = $node->value;
            $resultC = $this->walk($node->right);
            $result  = [$resultA, $resultB, $resultC];
            $this->reduce($result, $callback);
            return $result;
        }
    }
 
    private function reduce($result, $callback)
    {
        if (!is_array($result)) {
            return $callback($result);
        }        
        foreach($result as $v) {
            if (is_array($v)) {
                $this->reduce($v, $callback);
            } else {
                $callback($v);
            }
        }
    }
    
    public function setCmpCallback(callable $callback)
    {
        $this->cmpCallback = $callback;
    }

    public function getCmpCallback()
    {
        return $this->cmpCallback;
    }
    
    /* Returns a flat list of the tree's values */
    protected function toList(BinaryNode $node)
    {
        $array = $this->walk($node);
        $list = [];
        $list = $this->flattenRecursive($array, $list);
        return $list;
    }
    
    /* Flattens a multidimensinoal array into a flat array */
    protected function flattenRecursive($val, array &$list)
    {
        if (is_scalar($val) && $val !== null) {
            $list[] = $val;
        } elseif (is_array($val)) {
            foreach ($val as $v) {
                $this->flattenRecursive($v, $list);
            }
        } elseif (!is_scalar($val) && !is_null($val)) {
            $type = gettype($val);
            throw new BinaryTreeException("Unexpected type '$type' in flattenRecursive!");
        }

        return $list;
    }
    
    /* Iterative Binary Tree Traversal -- uses stack for in order traversal */
    public function inOrderIterativeTraversal()
    {
        $stack = $list = [];
        $current = $this->root;
        while($stack || $current) {
            if ($current) {
                $stack[] = $current;
                $current = $current->left;
            } else {
                $current = array_pop($stack);
                $list[] = $current;
                $current = $current->right;
            }
        }
        return $list;
    }
    
    /* Graphviz Draw - Draws the binary tree using graphviz notation */
    public function graphVizDraw()
    {
        $out = "digraph G{\ngraph [ordering=\"out\"]\n";
        $name = "";
        $stack = [];
        $current = $this->root;
        while($stack || $current) {
            if ($current && $current->parent) {
                $name = "$current->parent";
            }
            $value = "$current";
            if ($name && $value) {
                $out .= "$name -> $value\n";
            } elseif ($value && !$name && $current && !$current->parent) {
                $out .= "$value\n";
            }
            if ($current) {
                $stack[] = $current;
                $current = $current->left;
            } else {
                $current = array_pop($stack);
                $current = $current->right;
            }
        }
        $out .= "}";
        return $out;
    }
    
    /* Convert the GraphViz .dot notation to a PNG using GraphViz */
    public function toPNG($fileName)
    {
        if (!extension_loaded('Imagick')) {
            throw new BinaryTreeException("Imagick extension is not loaded. This method requires imagick...");
        }
        $dotData = $this->graphVizDraw();
        $img = new Imagick;
        $img->readImageBlob($dotData);
        $img->setImageFormat("png");
        file_put_contents($fileName, $img->getImageBlob());
        return $fileName;
    }
    
    /* Iterator Interface Implementation relies on iterative binary tree traversal */
    public function getIterator()
    {
        return new BinaryTreeIterator($this->inOrderIterativeTraversal());
    }
    
}

class BinaryTreeIterator implements Iterator
{
    private $list;
    
    public function __construct(Array $list = null)
    {
        $this->list = $list;
    }
    
    public function rewind()
    {
        reset($this->list);
    }
    
    public function next()
    {
        return next($this->list);
    }
    
    public function current()
    {
        return current($this->list);
    }
    
    public function key()
    {
        return key($this->list);
    }
    
    public function valid()
    {
        return key($this->list) !== null;
    }
}

class BinaryTreeException extends Exception
{
    /* Exception subtype for BinaryTree */
}
 
class BranchType
{
    /* Metatype for branch */
}
 
class LeftBranch extends BranchType
{
    /* Metatype for left branch */
    public function __toString()
    {
        return "LeftBranch";
    }
}
 
class RightBranch extends BranchType
{
    /* Metatype for right branch */
    public function __toString()
    {
        return "RightBranch";
    }
}

class RootBranch extends BranchType
{
    /* Metatype for root nodes with no branch */
    public function __toString()
    {
        return "RootBranch";
    }
}
 
class BinaryNode
{
    protected $left, $right, $parent, $branch, $value, $tree;
    private $isRoot = false;
 
    public function __construct(BinaryTree $tree, BinaryNode $parent = null,
                                BranchType $branch = null, $value = null)
    {
        $this->tree   = $tree;
        $this->parent = $parent;
        $this->value  = $value;
        $this->branch = $branch;
    }
 
    public function __get($key)
    {
        if ($key === 'isRoot') {
            if ($this->parent === null) {
                return true;
            } else {
                return false;
            }
        } elseif ($key === 'left') {
            return $this->left;
        } elseif ($key === 'right') {
            return $this->right;
        } elseif ($key === 'parent') {
            return $this->parent;
        } elseif ($key === 'branch') {
            if (!$this->branch && !$this->parent) {
                return new RootBranch;
            } else {
                return $this->branch;
            }
        } elseif ($key === 'value') {
            return $this->value;
        }
    }
    
    public function __set($key, $value)
    {
        if ($key === 'isRoot') {
            return;
        } elseif ($key === 'left') {
            if ($value instanceof BinaryNode || is_null($value)) {
                $this->left = $value;
                if ($value) {
                    $value->branch = new LeftBranch;
                }
            } else {
                $type = gettype($value);
                throw new BinaryNodeException("Can only assign type BinaryNode to Binary Tree. Got".
                                              " type '$type' instead.");
            }
        } elseif ($key === 'right') {
            if ($value instanceof BinaryNode || is_null($value)) {
                $this->right = $value;
                if ($value) {
                    $value->branch = new RightBranch;
                }
            } else {
                $type = gettype($value);
                throw new BinaryNodeException("Can only assign type BinaryNode to Binary Tree. Got".
                                              " type '$type' instead.");
            }
        } elseif ($key === 'parent') {
            if ($value instanceof BinaryNode || is_null($value)) {
                $this->parent = $value;
                if ($value) {
                    $value->branch = null;
                    $value->parent = null;
                }
            } else {
                $type = gettype($value);
                throw new BinaryNodeException("Can only assign type BinaryNode or NULL to Binary".
                                              " Tree parent. Got type '$type' instead.");
            }
        } elseif ($key === 'branch') {
            if ($value instanceof RightBranch || $value instanceof LeftBranch || is_null($value)) {
                if (!$this->isRoot && !$value) {
                    throw new BinaryNodeException("Cannot assign null to non-root BinaryNode!");
                }
                $this->branch = $value;
            } else {
                $type = gettype($value);
                throw new BinaryNodeException("Can only assign type BranchType to BinaryNode".
                                              " branch. Got type '$type' instead.");
            }
        } elseif ($key === 'value') {
            // If the value is null we simply delete the node
            if ($value === null) {
                $this->getTree()->delete($this);
                return;
            }
            $tree = $this->getTree();
            // If the value already exists in the tree then do nothing
            if ($tree->search($value) !== false) {
                return;
            }
            // Otherwise we replace this node for a new one with the given value
            $this->delete();
            // Now add the new value back into the tree
            $tree->add($value);
        }
    }
    
    public function __toString()
    {
        return (string) $this->value;
    }
 
    public function add($value)
    {
        $callback = $this->getTree()->getCmpCallback();
        $cmp = $callback($value, $this->value);
        if (isset($this->value) && $cmp == 1) {
            if (!isset($this->right)) {
                $this->right = new BinaryNode($this->tree, $this, new RightBranch, $value);
            } else {
                $this->right->add($value);
            }
        } elseif (isset($value) && $cmp == -1) {
            if (!isset($this->left)) {
                $this->left = new BinaryNode($this->tree, $this, new LeftBranch, $value);
            } else {
                $this->left->add($value);
            }
        } elseif (!isset($this->value)) {
            $this->value = $value;
        }
    }
    
    public function getTree()
    {
        return $this->tree;
    }
    
    public function delete()
    {
        $this->getTree()->delete($this);
    }
}

class BinaryNodeException extends Exception
{
    /* Exception subtype for BinaryNode */
}

Examples

$btree = new BinaryTree;

Add Nodes

foreach([16,14,17,13,19,20,21,23] as $value) {
    $btree->add($value);
}

Traverse with foreach

foreach($btree as $k => $v) {
    echo "$k: $v\n";
}


0: 13
1: 14
2: 16
3: 17
4: 19
5: 20
6: 21
7: 23

Delete a Node

$btree->search(19)->delete();
echo "\n";
foreach($btree as $k => $v) {
    echo "$k: $v\n";
}


0: 13
1: 14
2: 16
3: 17
4: 20
5: 21
6: 23

Find a Node by Value

$node = $btree->search(14);
echo $node;

14

Replace a Node

$node->value = -14; // changing a node's value automatically replaces the node in the tree
echo "\n";
foreach($btree as $k => $v) {
    echo "$k: $v\n";
}

0: -14
1: 13
2: 16
3: 17
4: 20
5: 21
6: 23

Using Custom Comparison Callback

$btree = new BinaryTree;
$btree->setCmpCallback(function ($a, $b) {
    if (strlen($a) > strlen($b)) {
        return 1;
    } elseif (strlen($b) > strlen($a)) {
        return -1;
    } else {
        return 0;
    }
});
$btree->add("Hello");
$btree->add("Hello PHP World!");
$btree->add("Hello PHP...");
$btree->add("Hello World");

foreach($btree as $k => $v) {
    echo "$k: $v\n";
}

0: Hello
1: Hello World
2: Hello PHP...
3: Hello PHP World!

Using BinaryTree::toPNG() Method

We can get a visual representation of the binary tree using the toPNG method, which relies on the graphVizDraw method that translates the tree into dot notation. If you have graphviz installed you can easily convert this to a PNG image with this method.

$btree = new BinaryTree;

$numbers = [107,104,94,117,111,123];

foreach($numbers as $num) {
    $btree->add($num);
}

echo $btree->toPNG("/home/googleguy/btree.png");

This gives us a PNG file like so...