<?php


class Node {

    public $data;
    public $next;

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

    }

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


}


class Stack {

    private $top;

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

    public function push($data) {

        $new = new Node($data);
        $new->next = $this->top;
        $this->top = &$new;

    }

    public function pop() {

        if($this->isEmpty()) throw new Exception("Stack is empty");
        $top = $this->top;
        $this->top = $this->top->next;
        return $top->getData();

    }

    public function peek() {

        if($this->isEmpty()) throw new Exception("Stack is empty");
        return $this->top->getData();
    }

    public function isEmpty() {
        return $this->top == NULL;
    }


}

class Queue {

    private $head;
    private $tail;

    public function __construct()
    {
        $this->head = $this->tail = NULL;
    }

    public function isEmpty() {
        return $this->head == NULL;
    }

    public function enqueue($data) {

        $new = new Node($data);
        if($this->tail == NULL) {
            $this->head = &$new;
        }
        else {
            $this->tail->next = &$new;
        }
        $this->tail = &$new;
    }

    public function dequeue() {
        if($this->isEmpty()) throw new Exception("Queue is empty");
        $head = $this->head;
        $this->head = $this->head->next;
        return $head->getData();
    }

}


class BTNode {

    public $data;
    public $left;
    public $right;

    public function __construct($data)
    {
        $this->data = $data;
        $this->left  = $this->right = NULL;

    }

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


}


class BinaryTree {

    private $root;

    public function __construct($root, $adiacence_list)
    {
        $nodes = array();
        foreach ($adiacence_list as $node => $leaves) {
            if(!isset($nodes[$leaves[0]]) && $leaves[0] != NULL) {
                $left = new BTNode($leaves[0]);
                $nodes[$leaves[0]] = $left;
            }
            if(!isset($nodes[$leaves[1]]) && $leaves[1] != NULL) {
                $right = new BTNode($leaves[1]);
                $nodes[$leaves[1]] = $right;
            }
            $this_node = new BTNode($node);
            if($leaves[0] != NULL) $this_node->left = &$nodes[$leaves[0]];
            if($leaves[1] != NULL) $this_node->right = &$nodes[$leaves[1]];
            $nodes[$node] = $this_node;
        }

        $this->root = &$nodes[$root];
        $nodes = NULL;


    }

    public function BFS() {

        $visited = array();
        $out = array();
        $queue = new Queue();

        $queue->enqueue($this->root);
        $visited[$this->root->getData()] = true;
        $out[]=$this->root->getData();


        while(!$queue->isEmpty()) {

            $current = $queue->dequeue();
            if($current->left != NULL && !isset($visited[$current->left->getData()])) {
                $queue->enqueue($current->left);
                $visited[$current->left->getData()] = true;
                $out[]= $current->left->getData();
            }
            if($current->right != NULL && !isset($visited[$current->right->getData()])) {
                $queue->enqueue($current->right);
                $visited[$current->right->getData()] = true;
                $out[]= $current->right->getData();
            }
            $visited[$current->getData()] = true;
        }

        return $out;

    }

    public function DFS() {

        $visited = array();
        $stack = new Stack();
        $out = array();

        $stack->push($this->root);
        $visited[$this->root->getData()] = true;
        $out[]= $this->root->getData();

        while (!$stack->isEmpty()) {

            $current = $stack->peek();
            if($current->left != NULL && !isset($visited[$current->left->getData()])) {
                $visited[$current->left->getData()] = true;
                $stack->push($current->left);
                $out[] = $current->left->getData();
                continue;
            }
            if($current->right != NULL && !isset($visited[$current->right->getData()])) {
                $visited[$current->right->getData()] = true;
                $stack->push($current->right);
                $out[] = $current->right->getData();
                continue;
            }
            $stack->pop();


        }

        return $out;

    }


}


$adiacence_list = array(
    'a' => array('b','c'),
    'b' => array(NULL,'e'),
    'c' => array(NULL, 'd')
);

$bt = new BinaryTree('a',$adiacence_list);
var_dump($bt->BFS());
var_dump($bt->DFS());