Binary Search Tree Commands
PHP
Hard
5 views
Problem Description
Commands: INSERT x, FIND x. Print YES/NO for FIND.
Input Format
First line q. Next q lines.
Output Format
Outputs for FIND.
Sample Test Case
Input:
6
INSERT 5
INSERT 2
INSERT 8
FIND 2
FIND 7
FIND 8
Official Solution
<?php
class BSTNode{
public $v; public $l=null; public $r=null;
function __construct($v){ $this->v=$v; }
}
class BST{
private $root=null;
function insert($x){
if($this->root===null){ $this->root=new BSTNode($x); return; }
$cur=$this->root;
while(true){
if($x===$cur->v) return;
if($x<$cur->v){
if($cur->l===null){ $cur->l=new BSTNode($x); return; }
$cur=$cur->l;
}else{
if($cur->r===null){ $cur->r=new BSTNode($x); return; }
$cur=$cur->r;
}
}
}
function find($x){
$cur=$this->root;
while($cur!==null){
if($x===$cur->v) return true;
$cur = ($x<$cur->v) ? $cur->l : $cur->r;
}
return false;
}
}
$inputLines=preg_split('/\\R/', rtrim(stream_get_contents(STDIN)));
if(!$inputLines || trim($inputLines[0])==='') exit;
$q=intval($inputLines[0]);
$bst=new BST(); $output=[];
for($i=1;$i<=$q;$i++){
$tokens=preg_split('/\\s+/', trim($inputLines[$i] ?? ''), 2);
$cmd=$tokens[0] ?? '';
$x=intval($tokens[1] ?? 0);
if($cmd==='INSERT') $bst->insert($x);
else $output[] = $bst->find($x) ? 'YES' : 'NO';
}
echo implode(PHP_EOL,$output);
?>
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!