Find the number of nodes that have only one child node

Constructing a binary tree can be done recursively. Let’s assume that the tree is constructed based on the user input. If the node does not exist, the user inputs 0, and if it does exist, it has a positive number.

Starting from the root, we can read the user input and continue in the direction of a subtree if the number was positive while stopping the recursion tree there if it was 0.

vals = map(int, input().split())   # Read the values of BST from the input
idx = 0                            # The current value index
root = Node(vals[idx])             # Set the value of the root node

def read(node: Node):              # Recursively read all the data in the tree
    if node.value == 0:            # If the current value is 0 => node doesn't exist
        return                     # So, we don't read its left and right children
    node.left = Node(vals[idx + 1])     # Set the value of the left node
    node.right = Node(vals[idx + 2])    # Set the value of the right node
    idx += 2                            # Update the current value index

    read(node.left)                # Ask the user for data from the left subtree
    read(node.right)               # Ask the user for data from the right subtree

Here you can notice that the number of nodes is not determined initially. The program recursively reads all the inputs starting from the left one and propagating all the way until the value of the node is 0. And then continues on to reading the values for the right one. This process continues until all the bottom nodes are set to 0 and there are no more inputs to read. So, for the tree pictured above, the input by the user can look like the following:

1       # root
2       # root.left
3       # root.right
4       # root.left.left
5       # root.left.right
0       # root.left.left.left does not exist           (no left  child of 4)
0       # root.left.left.right does not exist          (no right child of 4)
0       # root.left.right.left does not exist          (no left  child of 5)
0       # root.left.right.right does not exist         (no right child of 5)
6       # root.right.left
7       # root.right.right
0       # root.right.left.left does not exist          (no left  child of 6)
0       # root.right.left.right does not exist         (no right child of 6)
8       # root.right.right.left
9       # root.right.right.right
0       # root.right.right.left.left does not exist    (no left  child of 8)
0       # root.right.right.left.right does not exist   (no right child of 8)
0       # root.right.right.right.left does not exist   (no left  child of 9)
0       # root.right.right.right.right does not exist  (no right child of 9)

This input can be represented as an array as well - [1, 2, 3, 4, 5, 0, 0, 0, 0, 6, 7, 0, 0, 8, 9, 0, 0, 0, 0] which would represent the binary tree. Here, instead of requesting the user to input a new number every time, we could iterate over the array and construct the binary tree recursively the same way as we’ve done above.

Given a valid binary tree, you are asked to calculate the number of nodes that have only a single child node.

Input

The input contains space-separated integers representing the values in the nodes of the binary tree. The order of the values is given as described above. A value of 0 means that the node does not exist.

Output

The program should print the number of nodes in a binary tree that have only one child.

Examples

Input	Output
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0	0
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0	1

Explanation

In the first example, the binary tree does not have any nodes with a single child

In the second example, the binary tree has only one node with a single child - the node with the number 3.

Pro tip 😎

You can modify the code above to create the nodes conditionally - only create a node and assign it to node.left or node.right if the inputted value is different from 0.

Constraints

Time limit: 1.5 seconds

Memory limit: 512 MB

Output limit: 1 MB