Binary Search Tree is also known as a ordered or sorted binary tree which is a node-based binary data structure .

Binary Search Tree has the following properties.

1. The left side subtree of a node should always contains only the nodes with the keys which is less than a node key.

2. The right side subtree of a node should always contains only the nodes with the keys which is greater than a node key.

3. It is must that the left and right subtree should be a binary tree as well.

4. There must be no duplicability between nodes each other.

In Below case, We use Binary Search Tree

It can be used as a quick and easy way to sort data list. You have to Insert data into a binary search tree at O(log(n)). Then to sort them you have to traverse the tree .

Binary Search Tree Example

/** Create Node Class **/
class Node
{
 public $parent = null;
 public $left = null;
 public $right = null;
 public $data = null;

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

 public function __toString()
 {
  return $this->data;
 }
}

/** Create BinarySearchTree Class **/ 
class BinarySearchTree
{
 protected $_root = null;

 protected function _insert(&$new, &$node)
 {
  if ($node == null) {
   $node = $new;
   return;
  }

  if ($new->data <= $node->data) {
   if ($node->left == null) {
    $node->left = $new;
    $new->parent = $node;
   } else {
    $this->_insert($new, $node->left);
   }
  } else {
   if ($node->right == null) {
    $node->right = $new;
    $new->parent = $node;
   } else {
    $this->_insert($new, $node->right);
   }
  }  
 }

 protected function _search(&$target,&$node)
 {
  if ($target == $node) {
   return 1;
  } else if ($target->data > $node->data && isset($node->right)) {
   return $this->_search($target, $node->right);
  } else if ($target->data <= $node->data && isset($node->left)) {
   return $this->_search($target, $node->left);
  }

  return 0;
 }

 public function insert($node)
 {
  $this->_insert($node, $this->_root);
 }

 public function search($item) 
 {
  return $this->_search($item, $this->_root);
 }
}

/* Add Data in Nodes **/
$node1 = new Node(43);
$node2 = new Node(52);
$node3 = new Node(44);
$node4 = new Node(47);
$node5 = new Node(65);

/* Create Object **/
$obj = new BinarySearchTree();

$obj->insert($node1);
$obj->insert($node2);
$obj->insert($node3);
$obj->insert($node4);
$obj->insert($node5);