Shortest Distance in a Binary Search Tree

Your task is to determine the shortest distance between two nodes with given keys in a Binary Search Tree (BST).

It is assured that both keys exist within the BST.

Input:

The first input line contains an integer 'T' denoting the number of test cases.
For each test case:
- The first line provides the BST elements in level order, separated by spaces. Use -1 for null nodes.
- The second line contains two space-separated integers, 'NODE1' and 'NODE2', which are the keys of the two specified nodes.

Output:

Output the shortest distance as an integer for each test case, representing the number of nodes in the path between 'NODE1' and 'NODE2', inclusive of both nodes.

Example:

Input:

1
6 3 8 2 4 7 10 -1 -1 -1 -1 -1 -1 9 14
6 14

Output:

4

Explanation:

The path from 6 to 14 in the BST is 6 -> 3 -> 8 -> 10 -> 14, so the distance is 4 nodes.

Constraints:

• 1 <= T <= 102
• 1 <= N <= 103 where N is the number of nodes in the BST.
• 1 <= Node.data <= 109
• The keys 'NODE1' and 'NODE2' are guaranteed to exist in the tree.
• Time Limit: 1 second

Note:

Implement the function; do not print the results.