Write a function destroyAllXs that, given a linked list of characters and a separate character, removes all Nodes with the given character from the list.
All remaining elements must appear in their original order.
Write a function infinitySnap that, given a binary search tree, removes and puts half the tree nodes into a new tree, and returns both trees.
This snap, however, is not random and takes every node in an even position, given a pre-order depth-first traversal.
The first tree should have the nodes in the odd positions.
The second tree should have the nodes in the even positions.
Example: if the order was ['a', 'b', 'c', 'd'], tree1 would have'a' and "c", and tree2 would have 'b' and d'.
If the BST is empty, return None.
Make a second function endgameSnap that takes the two binary search trees and restores them to the original binary tree.
Write your own preorder function as part of quiz6.py and use that in your part 2 code.
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.import unittest
from node import Node
from treenode import TreeNode
from unorderedlist import UnorderedList
from binarysearchtree import BinarySearchTree
def destroyAllXs(linkedList, character):
while(not linkedList.isEmpty() and linkedList.search(character)):
def preOrder(bst, lst):
if bst is not None: