BST

//1. За да разберем дали елементът вече съществува, използваме методът Search. Той връща стойност True при същестувавенто на такъв елемент. В двата метода рекурсивен и нерекурсивен, добавяме проверка !Search(root,v) в случаите в които се добавя отляво или отдясно. В Source кодът няма нерекурсивен метод за търсачка и заради това и в двата метода използвам Search методът.

        //рекурсивна реализация на добавяне на елемент
        public void Add(ref Node root, int v)
        {
            if (root == null)
            {
                root = new Node();
                root.value = v;
            }
            else if (v < root.value)
            {
                if(!Search(root,v))
                {
                    Add(ref root.left, v);
                }
                else
                {
                    Console.WriteLine($"The value {v} already exists!");
                }
            }
            else
            {
                if (!Search(root, v))
                {
                    Add(ref root.right, v);
                }
                else
                {
                    Console.WriteLine($"The value {v} already exists!");
                }
            }
        }

        //нерекурсивна реализация на добавяне на елемент
        public void AddNR(ref Node root, int v)
        {
            if (root == null)
            {
                root = new Node();
                root.value = v;
            }
            else
            {
                Node newNode = new Node();
                newNode.value = v;
                Node prior = root;
                Node next;
                if (v < root.value)
                {
                    if (Search(root, v))
                    {
                        Console.WriteLine($"The value {v} exists!");
                        return;
                    }
                    next = root.left;
                }
                else
                {
                    if (Search(root, v))
                    {
                        Console.WriteLine($"The value {v} exists!");
                        return;
                    }
                    next = root.right;
                }
                while (next != null)
                {
                    prior = next;
                    if (v < prior.value)
                        next = prior.left;
                    else
                        next = prior.right;
                }
                if (v < prior.value)
                    prior.left = newNode;
                else
                    prior.right = newNode;
            }
        }


// Задача 2

        public static bool SearchNodeNR(Node root, int key)
        {
            Node parent; // Променлива която да сочи към родител на даденият нод

            Node curr = root; // Започваме със началният нод

            while (curr != null && curr.value != key)
            {
                parent = curr; // Всеки път задаваме стойността на новият родител за даденият нод

                if (key < curr.value)
                {
                    curr = curr.left;
                }
                else
                {
                    curr = curr.right;
                }
            }
            return curr != null;
        }

// Алтернативен нерекурсивен начин за намиране (По-дълъг)
public bool SearchNR(Node root, int key)
        {
            Node searchNode = new Node();
            searchNode.value = key;
            Node prior = root;
            Node next;
            if (key < root.value)
            {
                next = root.left;
            }
            else
            {
                next = root.right;
            }
            while (next != null)
            {
                prior = next;
                if (key < prior.value)
                    next = prior.left;
                else
                    next = prior.right;

            }
            if(key == prior.value)
            {
                return prior.left == searchNode;
            }
            else
            {
                return prior.right == searchNode;
            }
        }

// Задача 3 - Използва се търсачка от 2ра задача (Но там методът е булев) След извикването на метода RemoveNode, в main трябва да се извика методът Traverse, за да видим резултатът.

public static Node RemoveNode(Node root, int key)
        {
            Node parent = null;
            Node curr = root;
            while (curr != null && curr.value != key)
            {
                parent = curr;
                if (key < curr.value)
                {
                    curr = curr.left;
                }
                else
                {
                    curr = curr.right;
                }
            }
            if (curr == null)
            {
                Console.WriteLine("They key is not found in the tree");
                return root;
            }
            // Първи случай когато е листо
            if (curr.left == null && curr.right == null)
            {
                if (curr != root) // Задаваме на бащата ляво/дясно да са null
                {
                    if (parent.left == curr)
                    {
                        parent.left = null;
                    }
                    else
                    {
                        parent.right = null;
                    }
                }
                else // Ако е само един го задавеме за null
                {
                    root = null;
                }
            }
            // Втори случай -> Ако нодът има само едно дете
            else
            {
                // Избираме син на нодът
                Node child = (curr.left != null) ? curr.left : curr.right;

                // Ако нодът, който ще изтрием, не е root нод задаваме бащите като деца
                if (curr != root)
                {
                    if (curr == parent.left)
                    {
                        parent.left = child;
                    }
                    else
                    {
                        parent.right = child;
                    }
                }
                else
                {
                    root = child;
                }
            }
            return root;
        }