using System;


namespace Lab3
{
    class TreeNode
    {
        static private Random Generator { get; } = new();

        public Int32 Value { get; }
        public Int32 Count => 1 + (Left?.Count ?? 0) + (Right?.Count ?? 0);
        public TreeNode Left { get; private set; }
        public TreeNode Right { get; private set; }

        public TreeNode(Int32 value) => Value = value;

        static public TreeNode Search(TreeNode tree, Int32 value)
        {
            if (tree is null)
                return null;

            if(tree.Value == value)
                return tree;
            else if(tree.Value > value)
                return Search(tree.Left, tree.Value);
            else if(tree.Value < value)
                return Search(tree.Right, tree.Value);
            else
                return null;
        }

        static public TreeNode InsertIntoRoot(TreeNode tree, Int32 value)
        {
            if (tree is null)
                return new TreeNode(value);

            if(value < tree.Value)
            {
                tree.Left = InsertIntoRoot(tree.Left, value);
                return RotateRight(tree);
            }
            else if(value > tree.Value)
            {
                tree.Right = InsertIntoRoot(tree.Right, value);
                return RotateLeft(tree);
            }
            else
            {
                return tree;
            }
        }
        static public TreeNode Insert(TreeNode tree, Int32 value)
        {
            if (tree is null)
                return new TreeNode(value);

            if (Generator.Next(tree.Count + 1) == 0)
                return InsertIntoRoot(tree, value);

            if (value < tree.Value)
                tree.Left = Insert(tree.Left, value);
            else if (value > tree.Value)
                tree.Right = Insert(tree.Right, value);

            return tree;
        }

        static public TreeNode RotateRight(TreeNode tree)
        {
            TreeNode newRoot = tree.Left;
            if (newRoot is null)
                return tree;

            tree.Left = newRoot.Right;
            newRoot.Right = tree;
            return newRoot;
        }
        static public TreeNode RotateLeft(TreeNode tree)
        {
            TreeNode newRoot = tree.Right;
            if (newRoot is null)
                return tree;

            tree.Right = newRoot.Left;
            newRoot.Left = tree;
            return newRoot;
        }
    }


    class Program
    {
        static void SymmetricPrint(TreeNode tree, int offset = 0)
        {
            if (tree is null)
                return;

            SymmetricPrint(tree.Left, offset + 1);
            Console.WriteLine(new string('=', offset) + tree.Value);
            SymmetricPrint(tree.Right, offset + 1);
        }
        static void BackwardPrint(TreeNode tree, int offset = 0)
        {
            if (tree is null)
                return;

            BackwardPrint(tree.Left, offset + 1);
            BackwardPrint(tree.Right, offset + 1);
            Console.WriteLine(new string('=', offset) + tree.Value);
        }
        static TreeNode ForwardCopy(TreeNode left, TreeNode right)
        {
            if (right is null)
                return left;

            left = TreeNode.Insert(left, right.Value);
            left = ForwardCopy(left, right.Left);
            left = ForwardCopy(left, right.Right);
            return left;
        }
        public static void Main(string[] args)
        {
            Random generator = new Random();

            TreeNode tree_1 = new TreeNode(generator.Next(100));
            for(int i = 0; i < 10; ++i)
                tree_1 = TreeNode.Insert(tree_1, generator.Next(100));

            TreeNode tree_2 = new TreeNode(generator.Next(100));
            for (int i = 0; i < 10; ++i)
                tree_2 = TreeNode.Insert(tree_2, generator.Next(100));


            Console.WriteLine("======================");
            SymmetricPrint(tree_1, 0);
            Console.WriteLine("======================");
            Console.WriteLine("======================");
            SymmetricPrint(tree_2, 0);
            Console.WriteLine("======================");
            tree_1 = ForwardCopy(tree_1, tree_2);
            Console.WriteLine("======================");
            SymmetricPrint(tree_1, 0);
            Console.WriteLine("======================");
        }
    }
}