Q2. [115] (Link-based) Binary Search Tree (BST) Implement a BST ADT that includes the following operations and other supporting (or required) operations in Python. For each operation, print its output with the given data. (k, e) - an item of (key, element). Vw - node 1) [15] Insert(k, e) : Create a binary search tree by inserting the following items, (k e), to an initial empty BST: (25,C),(35,G),(45, B), (20,P), (30,0), (5, 2), (55, L), (43, F), (22, A), (6, U), (8, N), (40, R) InOrder(v): Then, Print the keys of the BST by InOrder traversal at a tree rooted at v. In the created BST in 1) 2) [10) root(): Return a root node of the tree and print its item. 3) [10] Search(k, v): Search/return a node whose key is 45 in the BST rooted at v, and print the returned item. 4) [10] Successor(v): a) Find/return a successor of a node v whose key is B and print its item. b) Then, find/return a successor of a node with a key 35, and print its item. 5) [10] Predecessor(v): a) Find/return a predecessor of a node whose key is 20 and print its key. b) Then, find/print the predecessor of a node with a key 40, and print its item. 6) [20] removeAbove External(w): Remove an external node wand its parent node v, then reconnect v's parent with w's sibling. Remove(k): Remove (a) a node whose key is 35, then remove (b) the node with a key 5 - Implement it with removeAbove External(w). PostOrder(): Then, (c) print the keys after each removal in 6.(a & b) by PostOrder traversal 7) [10] rangeQuery(k1, K2, v): find and print the keys in the range of [25. 45). 8) [10] is External(): Test whether a node v with a key 40 is an external node or not. re iant). Tarhanadh aftenent 6) [20] removeAbove External(w): Remove an external node wand its parent nodev, then reconnect V's parent with w's sibling. Remove(k): Remove (a) a node whose key is 35, then remove (b) the node with a key 5 -Implement it with removeAbove External(w). PostOrder(v): Then, (C) print the keys after each removal in 6.(a & b) by PostOrder traversal. 7) [10] rangeQuery(k1, k2, v): find and print the keys in the range of [25, 45). 8) [10] is External(v): Test whether a node v with a key 40 is an external node or not. 9) [5] isRoot(v): Test whether a node v with a key 25 is the root of BST or not. 10) [15] Implement the LCA(v, w) algorithm of Q1 and find/print the key of LCA[v, w) where a) [5] v.key = 30, w.key = 40 b) [5] v.key = 6, w.key = 55 c) [5] v.key = 35, w.key = 45