C++

CS212- Data Structures and Algorithms Assignment Due Date: 13-1-2021 Question 1: (Linked List) Write a function that takes three arguments a pointer to a linked list of integers and two integers, n and j-and inserts n after the jth element of the list. Ifjis 0, nis inserted at the head of the list. If j is greater than the number of elements in the list, n is inserted after the last one. Question 2: (Stack) A stack, S1, contains some numbers in arbitrary order. Using another stack, S2, for temporary storage, show how to sort the numbers in SI such that the smallest is at the top of S1 and the largest is at the bottom Question 3: (BST) The lowest common ancestor (LCA) of two nodes x and y in the BST is the lowest (i.c.. deepest) node that has both x and y as descendants, where each node can be a descendant of itself (so if x is reachable from w, w is the LCA). In other words, the LCA of x and y is the shared ancestor of x and y that is located farthest from the root. Given a BST and two nodes x and y in it, write a function that returns the lowest common ancestor (LCA) of x and y. For example, consider the following BST: 15 LCA (6, 12) = 10 LCA (10, 12) = 10 LCA (20, 6) = 15 LCA (18, 22) = 20 LCA (30, 30) = 30 10 25 12 20 30 18 22 Lowest Common Ancestor in BST