using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

    }

    // 1. Implement a function to ckeck if a binary tree is balanced, i.e. the heights of the two subtrees of any node never differ by more than one

    //

    public static int Task1(Node node)

    {

        if (node.Left == null && node.Left == null)

            return 1;

        if (node.Left == null || node.Right == null)

            return -1;

​

        var h1 = Task1(node.Right);

        if (h1 == -1)

            return -1;

        var h2 = Task1(node.Left);

        if (h2 == -1 || Math.Abs(h1 - h2) > 1)

            return -1;

        else

            return h1 + 1;

    }

    // 2. Given a directed graph, design an algorithm to find out whether there is a route between two nodes

    //

    public static bool Task2(Node node1, Node node2)

    {

        var queue = new Queue<Node>();

        queue.Enqueue(node1);

        while(queue.Count > 0)

        {

            var node = queue.Dequeue();

            if (node1.Equals(node2))

                return true;

            foreach(var child in node.Adjacent)

            {

                if (!child.IsVisited)

                    queue.Enqueue(child);

            }

            node.IsVisited = true;

        }

        return false;

    }

    // 3. Given a sorted (increasing order) array with the unique integer elements, write an algorithm to create a binary search tree with minimal height

    //

    public static Node Task3(int[] array, int start, int end)

    {

        if (start == end)

            return new Node() { Data = array[start] };

​

        var middle = (start + end)/2;

        var node = new Node();

        node.Left = Task3(array, start, Math.Max(middle, middle - 1));

        node.Right = Task3(array, Math.Min(middle + 1, end), end);

        node.Data = array[middle];

        return node;

    }

    // 4. Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you'll have D linked lists)

    //

    public List<Node> Task4(Node root)

    {

        var result = Task4_Helper(new List<Node> { root });

        result.Reverse();

        return result;

    }

    //

    public List<Node> Task4_Helper(List<Node> level)

    {

        if (level.Count == 0)

            return new List<Node>();

        var newLevel = new List<Node>();

        Node previous = null;

        foreach(var node in level)

        {

            if (previous != null)

                previous.Next = node;

            previous = node;

            newLevel.Add(node.Left);

            newLevel.Add(node.Right);

        }

        var result = Task4_Helper(newLevel);

        result.Add(level.First());

        return result;

    }

    // 5. Implement a function to check if a binary tree is a binary search tree 

    //

    public bool Task5(Node root)

    {

        return Task5_Helper(root, int.MinValue, int.MaxValue);

    }

    //

    public bool Task5_Helper(Node node, int min, int max)

    {

        if (node == null)

            return true;

        if (node.Data > max || node.Data <= min)

            return false;

        if (!Task5_Helper(node.Left, min, node.Data))

            return false;

        if (!Task5_Helper(node.Right, node.Data, max))

            return false;

        return true;

    }

    // 6. Write an algprithm to find the 'next' node (i.e., in-order successor) of a given node in a BST. You may assume that each node has a link to its parent

    public Node Task6(Node node)

    {

        if (node == null)

            return null;

        Node helper = node.Right;

        if (helper != null)

        {

            while(helper.Left != null)

                helper = helper.Left;

            return helper;

        }

        while(node.Parent != null && node.Parent.Left != node)

        {

            node = node.Parent;

        }

        return node.Parent;

    }

}

​

public class Node

{

    public List<Node> Adjacent { get; set; }

    public Node Left { get; set; }

    public Node Right { get; set; }

    public bool IsVisited { get; set; }

    public int Data { get; set; }

    public Node Next { get; set; }

    public Node Parent { get; set; }

}

​

​