Remove Half Nodes

You are given a binary tree and you need to remove all the half nodes (which have only one child). Return the root node of the modified tree after removing all the half-nodes.

Note: The output will be judged by the inorder traversal of the resultant tree, inside the driver code.

Examples:

Input: tree = 5
            /   \
          7     8
        / 
      2
Output: 2 5 8
Explanation: In the above tree, the node 7 has only single chile. After removing the node the tree becomes  2<-5->8. Hence, the answer is 2 5 8 & it is in inorder traversal.

Input:  tree = 2   
              / \   
            7   5 
Output: 7 2 5
Explanation: Here there are no nodes which has only one child. So the tree remains same.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(height of the binary tree)

Constraints:
1<=number of nodes<=10⁴

Approach 01

class Solution {
public:
    Node* RemoveHalfNodes(Node* root) {
        // Base case: if the node is NULL or is a leaf node, return the node itself
        if (!root || (!root->left && !root->right)) {
            return root;
        }

        // Recursively remove half nodes from the left and right subtrees
        root->left = RemoveHalfNodes(root->left);
        root->right = RemoveHalfNodes(root->right);

        // If the node has only a right child, return the right child
        if (!root->left) {
            return root->right;
        }

        // If the node has only a left child, return the left child
        if (!root->right) {
            return root->left;
        }

        // If the node has both children, return the node itself
        return root;
    }
};

class Solution:
    def RemoveHalfNodes(self, root):
        
        # Base case: if the node is None or is a leaf node, return the node itself
        if not root or (not root.left and not root.right):
            return root
        
        # Recursively remove half nodes from the left and right subtrees
        root.left = self.RemoveHalfNodes(root.left)
        root.right = self.RemoveHalfNodes(root.right)
        
        # If the node has only a right child, return the right child
        if not root.left:
            return root.right
        
        # If the node has only a left child, return the left child
        if not root.right:
            return root.left
        
        # If the node has both children, return the node itself
        return root

Time Complexity

• Traversal:

  The algorithm traverses each node of the binary tree exactly once. Therefore, the traversal takes \( O(n) \) time, where \( n \) is the number of nodes in the tree.

• Overall Time Complexity:

  The overall time complexity is \( O(n) \).

Space Complexity

• Auxiliary Space:

  The auxiliary space is primarily used for the recursion stack. In the worst case, the recursion stack can go as deep as the height of the binary tree. Therefore, the space complexity is \( O(h) \), where \( h \) is the height of the tree.

• Overall Space Complexity:

  The overall space complexity is \( O(h) \).