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$

$=$

$1$

$1$

Expected Output: DLList containing node with value

$5$

$($

the only common ancestor

$)$

Example

$2$

: Both values found

val

$1$

$=$

$5$

val

$2$

$=$

$1$

$9$

Expected Output: DLList containing nodes with values

$1$

$5$

$,$

$$and

$2$

$0$

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. using only #include WITHOUT using vector STL or anything related