DS1

namespace BinaryTreeMerge;

public class Program
{
    public static void Main()
    {
        var tree1 = new BinaryTree();
        tree1.Insert(3);
        tree1.Insert(1);
        tree1.Insert(2);

        var tree2 = new BinaryTree();
        tree2.Insert(2);
        tree2.Insert(8);
        tree2.Insert(5);

        var mergedTree = BinaryTree.Merge(tree1, tree2);
    }
}

public class TreeNode
{
    public int Value { get; }
    public TreeNode Left { get; set; }
    public TreeNode Right { get; set; }

    public TreeNode(int value)
    {
        Value = value;
    }
}

public class BinaryTree
{
    public TreeNode Root { get; set; }

    public void Insert(int value)
    {
        if (Root == null)
        {
            Root = new TreeNode(value);
            return;
        }

        var currentNode = Root;
        var newNode = new TreeNode(value);

        while (true)
        {
            if (value < currentNode.Value)
            {
                if (currentNode.Left == null)
                {
                    currentNode.Left = newNode;
                    return;
                }
                currentNode = currentNode.Left;
            }
            else
            {
                if (currentNode.Right == null)
                {
                    currentNode.Right = newNode;
                    return;
                }
                currentNode = currentNode.Right;
            }
        }
    }

    public static BinaryTree Merge(BinaryTree tree1, BinaryTree tree2)
    {
        if (tree1 == null || tree1.Root == null) return tree2;
        if (tree2 == null || tree2.Root == null) return tree1;

        var minTree = tree1.Root.Value <= tree2.Root.Value ? tree1 : tree2;
        var maxTree = minTree == tree1 ? tree2 : tree1;
        var maxNode = FindLargestNode(minTree.Root);

        maxNode.Right = maxTree.Root;

        return minTree;
    }

    private static TreeNode FindLargestNode(TreeNode node)
    {
        while (node.Right != null) node = node.Right;
        return node;
    }
}