using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        BinarySearchTree bst = new BinarySearchTree();

        int[] values = {3, 5, 1, 7, 8, 0, 9};

        foreach(var item in values)

        {

            bst.Insert(item);

        }

        bst.PreorderTraversal();

        bst.BreadthFirstTraversal();

        ///////////////////////////////////////////

         // Пример использования

        ListNode<int> list1 = new ListNode<int>(1, new ListNode<int>(2, new ListNode<int>(3)));

        ListNode<int> list2 = new ListNode<int>(4, new ListNode<int>(5));

​

        Console.WriteLine("Original List 1:");

        PrintList(list1);

​

        Console.WriteLine("Original List 2:");

        PrintList(list2);

​

        ListNode<int> newList = LinkedListOperations<int>.ReplaceElement(list1, 2, 10);

​

        Console.WriteLine("List 1 after replacing element 2 with 10:");

        PrintList(newList);

​

        ListNode<int> concatenatedList = LinkedListOperations<int>.ConcatenateLists(list1, list2);

​

        Console.WriteLine("Concatenated List:");

        PrintList(concatenatedList);

    }

      static void PrintList(ListNode<int> list)

    {

        while (list != null)

        {

            Console.Write(list.Value);

            list = list.Next;

        }

​

        Console.WriteLine();

    }

}

​

​

​

public class TreeNode

{

    public int Value { get; set; }

    public TreeNode Left { get; set; }

    public TreeNode Right { get; set; }

​

    public TreeNode(int value)

    {

        Value = value;

        Left = null;

        Right = null;

    }

}

​

public class BinarySearchTree

{

    private TreeNode root;

​

    public void Insert(int value)

    {

        root = InsertNode(root, value);

    }

​

    private TreeNode InsertNode(TreeNode node, int value)

    {

        if (node == null)

        {

            return new TreeNode(value);

        }

​

        if (value < node.Value)

        {

            node.Left = InsertNode(node.Left, value);

        }

        else if (value > node.Value)

        {

            node.Right = InsertNode(node.Right, value);

        }

​

        return node;

    }

​

    public void PreorderTraversal()

    {

        Console.WriteLine("Preorder Traversal:");

        PreorderTraversal(root);

        Console.WriteLine();

    }

​

    private void PreorderTraversal(TreeNode node)

    {

        if (node != null)

        {

            Console.Write(node.Value + " ");

            PreorderTraversal(node.Left);

            PreorderTraversal(node.Right);

        }

    }

​

    public void BreadthFirstTraversal()

    {

        Console.WriteLine("Breadth-First Traversal:");

        BreadthFirstTraversal(root);

        Console.WriteLine();

    }

​

    private void BreadthFirstTraversal(TreeNode root)

    {

        if (root == null)

        {

            return;

        }

​

        Queue<TreeNode> queue = new Queue<TreeNode>();

        queue.Enqueue(root);

​

        while (queue.Count > 0)

        {

            TreeNode current = queue.Dequeue();

            Console.Write(current.Value + " ");

​

            if (current.Left != null)

            {

                queue.Enqueue(current.Left);

            }

​

            if (current.Right != null)

            {

                queue.Enqueue(current.Right);

            }

        }

    }

}

​

//////////////////////////////////////////////////////////////////////////////

public class ListNode<T>

{

    public readonly T Value;

    public readonly ListNode<T> Next;

​

    public ListNode(T value, ListNode<T> next = null)

    {

        Value = value;

        Next = next;

    }

​

    public ListNode<T> ReplaceNext(ListNode<T> newNext)

    {

        return new ListNode<T>(Value, newNext);

    }

}

​

public class LinkedListOperations<T>

{

    public static ListNode<T> ReplaceElement(ListNode<T> head, T oldValue, T newValue)

    {

        if (head == null)

            return null;

​

        if (head.Value.Equals(oldValue))

            return new ListNode<T>(newValue, head.Next);

​

        var newNext = ReplaceElement(head.Next, oldValue, newValue);

        return head.ReplaceNext(newNext);

    }

​

    public static ListNode<T> ConcatenateLists(ListNode<T> list1, ListNode<T> list2)

    {

        if (list1 == null)

            return list2;

​

        return new ListNode<T>(list1.Value, ConcatenateLists(list1.Next, list2));

    }

}

​