Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms
• 10
Basic Dynamic Programming
• 11
Recursion
• 12
• 13
Queue & Stack
• 14
Binary tree + BST
• 15
Divide & Conquer + Advanced Sorting
• 16
Heap
• 17
Hashing
• 18
Graph Representation

• # 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

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

1. In the first example, the binary tree does not have any nodes with a single child
1. 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