<?php

/*
 *
 * @author: barce[a t]codebelay.com
 *
 */
class BinTreeNode {

	var $value;
	var $right;
	var $left;

	function __construct($value) {
		if(!is_int($value)) { return false; }
		$this->value = $value;
	}

}


function insert($leaf, $i_query) {
	if ($i_query < $leaf->value) {
		if (isset($leaf->left)) { 
			insert($leaf->left, $i_query);
		} else {
			$leaf->left = new BinTreeNode($i_query);
		}
	} else if ($i_query > $leaf->value) {
		if (isset($leaf->right)) { 
			insert($leaf->right, $i_query);
		} else {
			$leaf->right = new BinTreeNode($i_query);
		}
	}
	return $leaf;
}


function search($leaf, $i_query) {

	if ($i_query < $leaf->value) {
		if (isset($leaf->left)) { 
			echo "taking a step left\n";
			$leaf = $leaf->left; 
			if ($i_query == $leaf->value) {
				echo "taking a step left\n";
				$leaf->left  = NULL;
				$leaf->right = NULL;
				return $leaf;
			} else if ((is_null($leaf->right)) && (is_null($leaf->left))) {
				return "not found\n";
			} else {
				$leaf = search($leaf, $i_query);
			}
		}
	} else if ($i_query > $leaf->value) {
		if (isset($leaf->right)) { 
			echo "taking a step right\n";
			$leaf = $leaf->right; 
			if ($i_query == $leaf->value) {
				$leaf->left  = NULL;
				$leaf->right = NULL;
				return $leaf;
			} else if ((is_null($leaf->right)) && (is_null($leaf->left))) {
				return "not found\n";
			} else {
				$leaf = search($leaf, $i_query);
			}
		}
	}

	return $leaf;
}


$tree = new BinTreeNode(12);
insert($tree, 8);
insert($tree, 22);
insert($tree, 14);
insert($tree, 23);
insert($tree, 2);
insert($tree, 5);
insert($tree, 1);
insert($tree, 10);

print "searching 1\n";
search($tree, 1);
print "searching 8\n";
search($tree, 8);
/*
for ($i = 0; $i <= 23; $i++) {
	print "---[$i]---\n";
	print_r(search($tree, $i));
}
*/

?>