Remove Half Nodes

Given a binary tree A with N nodes.

You have to remove all the half nodes and return the final binary tree.

NOTE:

• Half nodes are nodes which have only one child.
• Leaves should not be touched as they have both children as NULL.

1 <= N <= 10⁵

First and only argument is an pointer to the root of binary tree A.

Return a pointer to the root of the new binary tree.

Input 1:

           1
         /   \
        2     3
       / 
      4

Input 2:

            1
          /   \
         2     3
        / \     \
       4   5     6

Output 1:

           1
         /   \
        4     3

Output 2:

            1
          /   \
         2     6
        / \

       4   5

Explanation 1:

 The only half node present in the tree is 2 so we will remove this node.

Explanation 2:

 The only half node present in the tree is 3 so we will remove this node.