Ex$1.$ Common Ancestors

Problem Description

Write a BST function named common$\_$ancestors that takes two values of templated type T as arguments:

DLList common$\_$ancestors$($const T & val$1,$ const T & val$2)$ const

The function should search the BST for these values and return a Doubly Linked List $($DLList$)$ containing the values of the common ancestors of val$1$ and val$2.$

Here's what the function should do in details:

If both val$1$ and val$2$ are found in the BST:

The function should return a DLList containing all the nodes that are ancestors of both val$1$ and val$2.$

If either val$1$ or val$2$ is not found in the BST:

The function should return an empty DLList.

Examples

Example $1$: Both values found

The function should assume the BST has unique values for each node $($no duplicate values$).$

val$1=4$

val$2=11$

Expected Output: DLList containing node with value $5($the only common ancestor$)$

Example $2$: Both values found

val$1=5$

val$2=19$

Expected Output: DLList containing nodes with values $15,$ and $20$

Example $3$: One or both values not found

val$1=7($not in the BST$)$

val$2=4$

Expected Output: Empty DLList

The function should assume the BST has unique values for each node $($no duplicate values$).$

Note. You are not allowed to declare any additional data members, but you can define helper functions in the private section of the BST class.