Predecessor and Successor in Binary Search Tree (BST)

Given a binary search tree (BST) with 'N' nodes, find the predecessor and successor of a given 'KEY' node in the BST.

Explanation:

The predecessor of a node in a BST is the node visited just before the given node in an inorder traversal. If the given node is first in the inorder, predecessor is NULL.

The successor of a node in a BST is the node visited immediately after the given node in an inorder traversal. If the given node is last in the inorder, successor is NULL.

Input:

The first line contains an integer 'T', the number of test cases.
Each test case consists of two lines:
- The first line contains the tree's elements in level order, separated by spaces. Use -1 for non-existent children.
- The second line contains 'KEY', the data of the node to find predecessor and successor.

Output:

For each test case, return two space-separated integers representing the predecessor and successor. If either does not exist, return -1 for that position.

Example:

Input:
1
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
KEY

Output:
-1 2

Constraints:

• 1 <= T <= 100
• 1 <= N <= 5000
• 0 <= data <= 106
• data ≠ -1