so I've been doing my research and I am trying to make a BST function in PHP. I've ran into a few problems, actually just one. When inserting a duplicate value, it will error out and the program crashes. I'm not exactly sure why this is occurring. I have inserted the class file below.
<?php
class Node{
public $value;
public $leftChild;
public $rightChild;
public function __construct($item){
$this->value = $item;
//new nodes are blank
$this->leftChild = null;
$this->rightChild = null;
}
public function inOrder(){
if($this->leftChild !== null){
$this->leftChild->inOrder();
}
print $this->value."</br>";
if($this->rightChild !== null){
$this->rightChild->inOrder();
}
}
public function preOrder(){
print $this->value."</br>";
if($this->leftChild !== null){
$this->leftChild->preOrder();
}
if($this->rightChild !== null){
$this->rightChild->preOrder();
}
}
public function postOrder(){
if($this->leftChild !== null){
$this->leftChild->postOrder();
}
if($this->rightChild !== null){
$this->rightChild->postOrder();
}
print $this->value."</br>";
}
}
class BinaryTree{
protected $root; //the root node of the tree
public function __construct(){
$this->root = null;
}
public function isEmpty(){
return $this->root === null;
}
public function insert($item){
//check if the tree is empty or if the current node is empty
if($this->isEmpty()){
//special case if tree is empty
$this->root = new Node($item);
}else{
//get the first node in the tree and begin the walk through
$current = $this->root;
while($current != null){
if($item < $current->value){
if($current->leftChild !== null){
$current = $current->leftChild;
}else{
$current->leftChild = new Node($item);
$current = $current->leftChild;
}
}elseif($item >= $current->value){
if($current->rightChild !== null){
$current = $current->rightChild;
}else{
$current->rightChild = new Node($item);
$current = $current->rightChild;
}
}else{
return;
}
//insert the node somewhere in the tree starting at the root
}
}
}
public function inOrderTraversal(){
//dump the tree rooted at "root"
$this->root->inOrder();
}
public function preOrderTraversal(){
//dump the tree rooted at "root"
$this->root->preOrder();
}
public function postOrderTraversal(){
$this->root->postOrder();
}
}
?>
This is the small snippet of code that I was using to display results
<?php
error_reporting(E_ALL);
require_once "assets/class/tree.class.php";
?>
<!DOCTYPE html>
<html>
<head>
<title></title>
</head>
<body>
<?
$array = array(1, 3, 2, 3, 4, 3, 2);
$tree = new BinaryTree();
for($i = 0; $i < count($array); $i++){
$tree->insert($array[$i]);
}
print_r($tree->inOrderTraversal());
?>
</body>
</html>
When doing some more research through my error logs I found this:
PHP Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 16 bytes) on line 77
I figure out my error. What was happening is that I was not allowing the loop to break out once a value was found. Thus creating an infinite loop. By adding breaks, I have solved this error.
while($current != null){
if($item < $current->value){
if($current->leftChild !== null){
$current = $current->leftChild;
}else{
$current->leftChild = new Node($item);
$current = $current->leftChild;
break;
}
}elseif($item >= $current->value){
if($current->rightChild !== null){
$current = $current->rightChild;
}else{
$current->rightChild = new Node($item);
$current = $current->rightChild;
break;
}
}else{
return;
}
//insert the node somewhere in the tree starting at the root
}