using python code

Q1. [10] Binary Tree Let T be a binary tree with n nodes. Define the Lowest Common Ancestor (LCA) between two nodes v and was the lowest node in T that has both v and was descendants. Given two nodes v and w. write an efficient algorithm. LCA(v, w), in a pseudo code for finding the LCA of vand w, using the structure of the tree, not the values of keys. I Note: Anode is a descendant of itself and v.depth gives a depth of a nodev. Q2. [115] (Link-based, Birlary 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 giver data. (k, e) - an item of (key, element), vw-node 1) [15] Insert(ke) : 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) 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 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] removeAbove External(w): Remove an external node w and 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 removeAboveExternal(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] isExternal(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 Q3. [25 pt.] Range Query in BST 1) [15] Implement a Range Query algorithm RangeQuery(ki, k2, v) in the BST ADT in Q2 to get the keys in the range [k1, k2] in the tree rooted at a nodev. 2) [10] Print the outputs in 1) where ki = 10 and k2 = 40. i.e. in the range [10, 40). in the BST of Q2.1. Q4. [20 pt. optional] Selection in BST 1) [10] Write an algorithm. SelectLi, v), in a pseudo code to get the its largest key of the BST rooted at a node v. 2) [10] Implement Selectl[i, v) in the BST ADT in Q2 and print the 86 largest key (ie. 1=8) in the BST of Q2.1)