<?php
class treeNode {
    public $data, $parent, $firstSon, $brother;

    public function __construct($data) {
        $this->data = $data;
        $this->parent = null;
        $this->firstSon = null;
        $this->brother = null;
    }
}

class Ntree {
    public $koren;

    public function __construct() {
        $this->koren = null;
    }

    public function addTreeNode($node, $valParent = null) {
        if ($this->koren == null) {
            $this->koren = $node;
            return "Корень успешно позажен со значением $node->data<br>";
        } elseif ($valParent == null) {
            return 'Введите значения родителя вставляемого элемента<br>';
        } elseif ($this->koren->data == $valParent){
            $node->parent = $this->koren;
            if ($this->koren->firstSon == null) {
                $this->koren->firstSon = $node;
                return "Вставка прошла успешно к корню! Вставлен элемент $node->data<br>";
            } else {
                $node->brother = $this->koren->firstSon->brother;
                $this->koren->firstSon->brother = $node;
                return "Вставка прошла успешно к корню! Вставлен элемент $node->data<br>";
            }
        } else {
            $path = [];
            $stack = new Stack();
            $stack->put($this->koren);
            while ($stack->last != null) {
                $curr = $stack->get();
                $path[$curr->data] = true;
                foreach ($this->getEdges($curr) as $node2) {
                    if ($node2->data == $valParent) {
                        $node->parent = $node2;
                        if ($node2->firstSon == null) {
                            $node2->firstSon = $node;
                            return "Вставка прошла успешно! Вставлен элемент $node->data<br>";
                        } else {
                            $node->brother = $node2->firstSon->brother;
                            $node2->firstSon->brother = $node;
                            return "Вставка прошла успешно (в брата)! Вставлен элемент $node->data<br>";
                        }
                    } elseif (!$path[$node2->data] && !$stack->contains($node2)) {
                        $stack->put($node2);
                    }
                }
            }
            return 'Такого родителя нет! <br>';
        }
    }

    function getEdges($node) {
        if ($node->firstSon)
            $currentSon = $node->firstSon;
            while ($currentSon != null) {
                yield $currentSon;
                $currentSon = $currentSon->brother;
            }
    }
}