php Binary Search Tree

bst.php

<?
/* 
  Itay Gutman <itaygutman@gmail.com>
*/

class Node
{

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

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

} //End class Node

class BST
{

	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 = $node;
			else{	
				if($node->data > $root->data) 
					$this->insertNode($root->right,$node); //Search for place in the right side to insert	
					
				if($node->data < $root->data) //Not using else to avoid duplicate values
					$this->insertNode($root->left,$node);  //Search for place in the left 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);
	}
	
	/* Get an array and insert all items in it to the tree in inc order */
	public function multiInsertSorted($array)
	{
	
		sort($array);
		$this->multiInsert($array);
	}	
	
	public function preOrder($node = NULL)
	{

		if($node === NULL) $node = $this->root; /* If node not selected the default is the tree root */
	
		echo $node->data.' ';
		
		if($node->left)
			$this->preOrder($node->left);
			
		if($node->right)
			$this->preOrder($node->right);
			
	} //End preOrder
	
	public function inOrder($node = NULL)
	{

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

		echo $node->data.' ';
			
		if($node->right)
			$this->inOrder($node->right);
			
	} //End inOrder	

	public function postOrder($node = NULL)
	{

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

		echo $node->data.' ';
			
	} //End inOrder	

	/* return the number of nodes in the tree */
	public function nodeCount($node = 'root')
	{

		if($node == 'root') $node = $this->root; /* If node not selected the default is the tree root, We use 'root' and not null here because null used for something else */
		
		if($node === NULL)
			return 0;
		else{
			if(!$node->left && !$node->right) //leaf
				return 1;
			else 
				return (1 + $this->nodeCount($node->left) + $this->nodeCount($node->right));
		}
			
	} //End nodeCount		
	
	/* return the number of leafs */
	public function leafCount($node = 'root')
	{
	
		if($node == 'root') $node = $this->root; /* If node not selected the default is the tree root, We use 'root' and not null here because null used for something else */
		
		if($node === NULL)
			return 0;
		else{
			if(!$node->left && !$node->right) //leaf
				return 1;
			else 
				return ($this->leafCount($node->left) + $this->leafCount($node->right));
		}	
		
	} //End leafCount 	
	
	/* Return the Node if the data is in the tree and FALSE if it is not exist */
	public function search($data,$node = 'root')
	{

		if($node === 'root') $node = $this->root; /* If node not selected the default is the tree root */
	
		if($node->data === NULL)
			return false;
		else{	
			if($node->data == $data)
				return $node;
			else{	
				if($data > $node->data)
					return $this->search($data,$node->right);		
				else
					return $this->search($data,$node->left);
			}		
		}		
	
	} //End search
	
	//return the biggest value in the tree
	public function max($node = NULL)
	{

		if($node === NULL) $node = $this->root; /* If node not selected the default is the tree root */
	
		if($node->right === NULL)
			return $node->data;
		else
			return $this->max($node->right);
			
	}
	
	//return the min value in the tree
	public function min($node = NULL)
	{
	
		if($node === NULL) $node = $this->root; /* If node not selected the default is the tree root */
			
		if($node->left === NULL)
			return $node->data;
		else
			return $this->min($node->left);
			
	}
	
	// return the tree height
	public function height($node = 'root')
	{

		if($node == 'root') $node = $this->root; /* If node not selected the default is the tree root */
		
		if($node === NULL)
			return 0;
		else
			return 1+max($this->height($node->right) , $this->height($node->left));
	}
	
	// remove a node from the tree
	public function remove($data,&$node = NULL ,&$parent = NULL)
	{

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

		if($data < $node->data){
			if($node->left != null)
				return $this->remove($data, $node->left , $node);
			else
				return false;
			}else if($data > $node->data){
				  if($node->right != null)
						return $this->remove($data, $node->right , $node);
				  else
						return false;
			}else{
					if($node->right && $node->left) { 
						$node->data = $this->min($node->right); //find the min value start with current node
						$this->remove($node->data, $node->right , $node);
					}
					else if ($parent->left == $node)
						$parent->left = ($node->left) ? $node->left : $node->right;
					else if ($parent->right == $node) 
						$parent->right = ($node->left) ? $node->left : $node->right;

					return true;
      }	
	} // End remove

	/*
	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 BST

/* ########### EXAMPLE ########### */
echo '<h1>Binary Search Tree</h1>';
$tree = new BST();
$tree->multiInsert(array(10,7,13,5,6,8,11,15,14,4,3));
$tree->insert(16);
$tree->remove(15);
echo '<br>Traval: PreOrder: ';
$tree->preOrder();
echo '<br>Traval: InOrder: ';
$tree->inOrder();
echo '<br>Traval: PostOrder: ';
$tree->postOrder();
echo '<br>Min: ';
echo $tree->min();
echo '<br>Max: ';
echo $tree->max();
echo '<br>Check if the number "5" is in the tree: ';
echo ($tree->search(5))? 'TRUE' : 'FALSE';
echo '<br>NodeCount: ';
echo $tree->nodeCount();
echo '<br>LeafCount: ';
echo $tree->leafCount();
echo '<br>Height:';
echo $tree->height();
echo'<br><br>';
echo $tree->draw();