22. [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) w-node 1) [15] Insertik, e): Create a binary search tree by inserting the following items, (ke), to an initial empty BST: (25,C),(35,G),(45, B), (20, P), (30, Q.5, Z), (55, L), (43, F), (22,A), (6, U), (8, N), (40, R) InOrdec(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] rooto: Return a root node of the tree and print its item. 3) [10] Searchk, 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 8 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] removeAboxe 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 remo move (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 PastQrder traversal. 7) [10] rangeQuery(k1, K2, v): find and print the keys in the range of [25, 45). 8) [10] isExternal(v): Test whether a node v with a key 40 is an external node or not. 9) [5isRoot(): Test whether a node v with a key 25 is the root of BST or not 10) [15] Implement the LCAC, W) algorithm of Q1 and find/print the key of LCA[v, w) where a) [5] w.key = 30. w.key= 40 b) [5] .key = 6 wkey= 55 1511 roi - 35 11 - 15 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] cemoveAkaveExternal(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 removeAkoxe External(w). PostOrder(v): Then, (c) print the keys after each removal in 6.[a & b) by Pastoesler traversal 7) [10) rangeQuery(k1, k2, v): find and print the keys in the range of [25, 45). 8) [10] isExternal(v): Test whether a node v with a key 40 is an external node or not. 9) [51.JsBoot(v): Test whether a node v with a key 25 is the root of BST or not. 10) [15] Implement the LCAC), w) algorithm of Q1 and find/print the key of LCA[v, w) where a) [5] .key = 30 w.kex = 40 b) [5] v.key = 6. w.key = 55 c) (5) v key = 35. W.key = 45
