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 subtreeHere 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: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB