Count Leaf Nodes in a Binary Tree

Count the number of leaf nodes present in a given binary tree. A binary tree is a data structure where each node has at most two children, known as the left child and the right child. A node is considered a leaf node if both of its child nodes are NULL.

Input:

The first line of input contains an integer 'T', representing the number of test cases. Each test case consists of a line containing elements of the binary tree in level order. If a node is null, it is represented by -1.

Output:

For each test case, output the number of leaf nodes present in the binary tree.

Example:

Input:

1
20 10 35 5 15 30 42 -1 13 -1 -1 -1 -1 -1 -1 -1

Output:

4

Explanation:

In the above example, nodes 5, 30, 42, and 13 are leaf nodes because they have no child nodes.

Constraints:

• 1 <= T <= 100
• 1 <= N <= 10^3
• 1 <= data <= 10^9
• Time Limit: 1 second