Maximum Sum of Non-Adjacent Nodes in a Binary Tree

Given a binary tree with integer values assigned to each node, select nodes such that their sum is maximum, ensuring no two adjacent nodes are picked.

Input:

The input consists of multiple test cases. The first line contains an integer 'T', the number of test cases.
For each test case, the binary tree is represented in level order in a single line with space-separated integers. Null nodes are represented by -1.
Example: 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output:

For each test case, output a single line with the maximum sum of non-adjacent nodes from the binary tree.

Example:

Consider the binary tree shown in the example image:

The maximum possible sum using non-adjacent nodes is 12.

Constraints:

• 1 <= T <= 100
• 0 <= N <= 3000 where N is the number of nodes in the binary tree.
• 1 <= data <= 10^4 where data is the node value of the binary tree.
• Time limit is 1 second per test case.

Note:

The tree nodes can only be summed according to adjacency rules, meaning if a node is chosen, its immediate children cannot be chosen.