Algorithms and Data Structures

  • Profound Academy

    • 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
        Linked LIst
      • 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.
    notion image
    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

    1. In the first example, the binary tree does not have any nodes with a single child
      1. notion image
    1. In the second example, the binary tree has only one node with a single child - the node with the number 3.
      1. notion image
     
    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

    To check your solution you need to sign in
    Sign in to continue