bst

bst.php

<?php

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

class BinarySearchTree
{
    public $root = null;
    
    public function insert($value)
    {
        if ($this->root === null)
        {
            $this->root = new Node($value);
        }
        else
        {
            $current = $this->root;
            $direction = null;
            
            while (true)
            {
                if ($value < $current->value)
                {
                    $direction = 'left';
                }
                else
                {
                    $direction = 'right';
                }
                
                if ($current->$direction === null)
                {
                    break;
                }
                
                $current = $current->$direction;
            }
            
            $current->$direction = new Node($value);
        }
    }
    
    public function has($value)
    {
        $unseen = [$this->root];
        
        while (count($unseen) !== 0)
        {
            $current = array_pop($unseen);
            
            if ($current !== null)
            {
                if ($current->value === $value)
                {
                    return true;
                }
                
                $unseen[] = $current->left;
                $unseen[] = $current->right;
            }
        }
        
        return false;
    }
    
    public function traverse_preorder()
    {
        $data = [$this->root];
        $index = 0;
        
        while ($index < count($data))
        {
            if ($data[$index]->left !== null)
            {
                $data[] = $data[$index]->left;
            }
            
            if ($data[$index]->right !== null)
            {
                $data[] = $data[$index]->right;
            }
            
            $index += 1;
        }
        
        for ($i = 0; $i < $index; $i += 1)
        {
            $data[$i] = $data[$i]->value;
        }
        
        return $data;
    }
    
    public function traverse_inorder()
    {
        return null; // TODO
    }
    
    public function size()
    {
        $unseen = [$this->root];
        $count = 0;
        
        while (count($unseen) !== 0)
        {
            $current = array_pop($unseen);
            
            if ($current !== null)
            {
                $count += 1;
                
                $unseen[] = $current->left;
                $unseen[] = $current->right;
            }
        }
        
        return $count;
    }
}

$bst = new BinarySearchTree();

$bst->insert(5);
$bst->insert(1);
$bst->insert(8);
$bst->insert(3);
$bst->insert(7);
$bst->insert(9);

/*
       .--5--.
      /       \
     1         8
      \       / \ 
       3     7   9
*/

var_dump($bst->size()); // 6

var_dump($bst->has(0)); // false
var_dump($bst->has(1)); // true
var_dump($bst->has(2)); // false
var_dump($bst->has(3)); // true
var_dump($bst->has(4)); // false
var_dump($bst->has(5)); // true
var_dump($bst->has(6)); // false
var_dump($bst->has(7)); // true
var_dump($bst->has(8)); // true
var_dump($bst->has(9)); // true

var_dump($bst->traverse_preorder()); // 5 1 8 3 7 9
var_dump($bst->traverse_inorder()); // 1 3 5 7 8 9