Binary Search Tree

In computer science, a Binary Search Tree (also known as ordered or sorted binary tree) is a node-based binary data structure which has the following properties.

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• The left and right subtree must each also be a binary tree.
• There must be no duplicate nodes.

In Following case, We use Binary Search Tree

They can be used as a quick way to sort data. Insert data into a binary search tree at O(log(n)). Then traverse the tree in order to sort them.

Binary Search Tree Example in PHP

/** 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);