Remove Half Nodes | Problem of the Day | GeeksForGeeks

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)

Table of Contents
0:00 Problem Statement
0:41 Solution
7:22 Pseudo Code
10:08 Code - Python
10:59 Code - C++

[mathematics]

Table of Contents
0:00 Problem Statement
0:41 Solution
7:22 Pseudo Code
10:08 Code - Python
10:59 Code - C++

[mathematics]

class Solution:
def RemoveHalfNodes(self, root):
if root is None:
return None

root.left =

root.right =

if root.left is None and root.right is None:
return root

if root.left is None:
return root.right


if root.right is None:
return root.left

return root

[mathematics]

class Solution {
public:
Node *RemoveHalfNodes(Node *root) {
if (!root)
return root;

root->left = RemoveHalfNodes(root->left);
root->right = RemoveHalfNodes(root->right);

if (!root->left and !root->right)
return root;

if (!root->left)
return root->right;

if (!root->right)
return root->left;

return root;
}
};