class bTreeNode
{
  private $value;
  public $left;
  public $right;

  function __construct($value, $left=null, $right=null) {
    $this->value = $value;
    $this->left = $left;
    $this->right = $right;
  }

  function getValue() {
    return $this->value;
  }
}

function depthFirstSearch($bTree, $value) {
  if (is_null($bTree)) {
    return null;
  }
  if ($bTree->getValue() === $value) {
    return $bTree;
  }
  $node = depthFirstSearch($bTree->left, $value);
  if ($node) {
    return $node;
  }
  return depthFirstSearch($bTree->right, $value);
}

function breadthFirstSearch($bTree, $value) {
  if (!$bTree) return null;
  $toSearch = [$bTree];
  while (count($toSearch)) {
    $node = array_shift($toSearch);
    if ($node->getValue() === $value) {
      return $node;
    }
    if ($node->left) {
      $toSearch[] = $node->left;
    }
    if ($node->right) {
      $toSearch[] = $node->right;
    }
  }
  return null;
}

# Testing bTree
$tree = new bTreeNode(50,
  new bTreeNode(25,
    new bTreeNode(12),
    new bTreeNode(40)
  ),
  new bTreeNode(75,
    new bTreeNode(60),
    new bTreeNode(80)
  )
);

print($tree->getValue().PHP_EOL);

# Depth First Search
$node = depthFirstSearch($tree, 5);
if ($node) {
  print($node->getValue().PHP_EOL);
}
else {
  print("No value found" . PHP_EOL);
}

$node = depthFirstSearch($tree, 12);
if ($node) {
  print($node->getValue().PHP_EOL);
}
else {
  print("No value found" . PHP_EOL);
}

# Breadth First Search
$node = breadthFirstSearch($tree, 5);
if ($node) {
  print($node->getValue().PHP_EOL);
}
else {
  print("No value found" . PHP_EOL);
}

$node = breadthFirstSearch($tree, 12);
if ($node) {
  print($node->getValue().PHP_EOL);
}
else {
  print("No value found" . PHP_EOL);
}