Given A binary Tree. Your task is to remove all the half nodes (which has only one child).
Example 1:
Input:
         7
       /   \
      7     8
     / 
    2
Output: 2 7 8 
Example 2:
Input:
         2
       /   \
      7     5
       \      \
        9      1
       /  \
      11   4
Output: 11 9 4 2 1 
Your Task:
You don't need to read input or print anything. Your task is to complete the function RemoveHalfNodes() which takes the root node of the tree as input and returns the root node of the modified tree after removing all the half nodes, ie the ones having just a single child node. (The inorder traversal of the returned tree is printed by the driver's code.)
For example consider the below tree.
Nodes 7, 5 and 9 are half nodes as one of their child is Null. We need to remove all such half nodes and return the root pointer of following new tree.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Binary Tree).
Constraints:
1<=Number of nodes<=10^{4}
Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Difficulty: EASY
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Binary Tree).

Starter code:
#User function Template for python3

# Return the root of the modified tree after removing all the half nodes.
def RemoveHalfNodes(root): 
    # code here.

Solutions:
def RemoveHalfNodes(root):
	if root is None:
		return None
	if root.left is None and root.right is None:
		return root
	if root.left is None:
		return RemoveHalfNodes(root.right)
	if root.right is None:
		return RemoveHalfNodes(root.left)
	root.left = RemoveHalfNodes(root.left)
	root.right = RemoveHalfNodes(root.right)
	return root


def RemoveHalfNodes(root):
	if root.left == None and root.right == None:
		return root
	if root.left == None and root.right:
		return RemoveHalfNodes(root.right)
	elif root.right == None and root.left:
		return RemoveHalfNodes(root.left)
	else:
		root.left = RemoveHalfNodes(root.left)
		root.right = RemoveHalfNodes(root.right)
	return root


def RemoveHalfNodes(root):
	if root.left is None and root.right is None:
		return root
	if root.left is None and root.right is not None:
		return RemoveHalfNodes(root.right)
	elif root.left is not None and root.right is None:
		return RemoveHalfNodes(root.left)
	else:
		root.left = RemoveHalfNodes(root.left)
		root.right = RemoveHalfNodes(root.right)
	return root


arr = []

def RemoveHalfNodes(root):
	if not root:
		return None
	root.left = RemoveHalfNodes(root.left)
	root.right = RemoveHalfNodes(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


def RemoveHalfNodes(root):
	if not root:
		return
	root.left = RemoveHalfNodes(root.left)
	root.right = RemoveHalfNodes(root.right)
	if root.left and (not root.right):
		return root.left
	if root.right and (not root.left):
		return root.right
	return root


def RemoveHalfNodes(root):
	prv = None

	def fun(root):
		if root is None:
			return
		root.left = fun(root.left)
		root.right = fun(root.right)
		if root.left and root.right is None:
			new_node = root.left
			temp = root
			root = None
			del temp
			return new_node
		if root.right and root.left is None:
			new_node = root.right
			temp = root
			root = None
			del temp
			return new_node
		return root
	return fun(root)


def RemoveHalfNodes(root):
	if root is None:
		return None
	root.left = RemoveHalfNodes(root.left)
	root.right = RemoveHalfNodes(root.right)
	if root.left == None and root.right == None:
		return root
	elif root.left != None and root.right == None:
		temp = root.left
		root = None
		return temp
	elif root.left == None and root.right != None:
		temp = root.right
		root = None
		return temp
	return root


def RemoveHalfNodes(root):
	new_root = x(root)
	return new_root

def x1(root, A):
	if root:
		A.append(root.data)
		x1(root.left, A)
		x1(root.right, A)

def x(root):
	if root:
		root.left = x(root.left)
		root.right = x(root.right)
		if root.left is None and root.right is not None:
			root = root.right
			return root
		elif root.left is not None and root.right is None:
			root = root.left
			return root
		return root


def RemoveHalfNodes(root):
	if not root or (not root.left and (not root.right)):
		return root
	root.left = RemoveHalfNodes(root.left)
	root.right = RemoveHalfNodes(root.right)
	if not root.left or not root.right:
		return root.left if root.left else root.right
	return root


def RemoveHalfNodes(root):

	def dfs(root):
		if not root:
			return None
		root.left = dfs(root.left)
		root.right = dfs(root.right)
		if not root.left and (not root.right):
			return root
		if not root.left:
			return dfs(root.right)
		if not root.right:
			return dfs(root.left)
		return root
	return dfs(root)


def isFullNode(root):
	if root.right and root.left or (not root.left and (not root.right)):
		return True
	return False

def RemoveHalfNodes(root):
	if not root:
		return None
	root.left = RemoveHalfNodes(root.left)
	root.right = RemoveHalfNodes(root.right)
	if isFullNode(root):
		return root
	if root.left:
		return root.left
	if root.right:
		return root.right


def Convert(Node):
	if Node == None:
		return (False, None)
	if Node.left == None and Node.right == None:
		return (True, Node)
	(LST, LNode) = Convert(Node.left)
	(RST, RNode) = Convert(Node.right)
	if LST and RST:
		Node.left = LNode
		Node.right = RNode
		return (True, Node)
	if LST and RST == False:
		Node.left = LNode
		return (True, LNode)
	if LST == False and RST:
		Node.right = RNode
		return (True, RNode)

def RemoveHalfNodes(root):
	(a, b) = Convert(root)
	return root


def solve(root):
	if root == None:
		return None
	elif root.left == None and root.right == None:
		return root
	else:
		l = solve(root.left)
		r = solve(root.right)
		if l == None:
			return r
		if r == None:
			return l
		root.left = l
		root.right = r
		return root

def RemoveHalfNodes(root):
	return solve(root)


def RemoveHalfNodes(root):
	if not root:
		return
	if not root.left and (not root.right):
		return root
	helper(root)
	return root

def helper(root):
	if not root:
		return
	if not root.left and (not root.right):
		return root
	if root.left and (not root.right):
		root.data = root.left.data
		a = None
		b = None
		if root.left.left:
			a = root.left.left
		else:
			a = None
		if root.left.right:
			b = root.left.right
		else:
			b = None
		root.left = None
		root.left = a
		root.right = b
		helper(root)
	if root.right and (not root.left):
		a = None
		b = None
		root.data = root.right.data
		if root.right.left:
			a = root.right.left
		else:
			a = None
		if root.right.right:
			b = root.right.right
		else:
			b = None
		root.right = None
		root.left = a
		root.right = b
		helper(root)
	helper(root.left)
	helper(root.right)


def RemoveHalfNodes(root):
	if root is None:
		return None
	root.left = RemoveHalfNodes(root.left)
	root.right = RemoveHalfNodes(root.right)
	if root.left is None and root.right is None:
		return root
	if root.left is None:
		new_root = root.right
		temp = root
		root = None
		del temp
		return new_root
	if root.right is None:
		new_root = root.left
		temp = root
		root = None
		del temp
		return new_root
	return root


def RemoveHalfNodes(root):

	def removeNode(root):
		if root == None:
			return root
		root.left = removeNode(root.left)
		root.right = removeNode(root.right)
		if root.left == None and root.right == None:
			return root
		if root.left == None:
			return root.right
		if root.right == None:
			return root.left
		return root
	return removeNode(root)


def RemoveHalfNodes(root):

	def solve(root):

		def find(root, prnt, x):
			if root == None:
				return None
			if root.left == None and root.right == None:
				return
			if prnt != None and root.left != None and (root.right == None):
				if x == 1:
					prnt.right = root.left
				else:
					prnt.left = root.left
				find(root.left, prnt, x)
			if prnt != None and root.left == None and (root.right != None):
				if x == 1:
					prnt.right = root.right
				else:
					prnt.left = root.right
				find(root.right, prnt, x)
			find(root.left, root, -1)
			find(root.right, root, 1)
		find(root, None, 0)
		return root
	z = solve(root)
	return z


def RemoveHalfNodes(root):

	def hasOne(root):
		if not root:
			return False
		if not root.left and (not root.right):
			return False
		if root.left and root.right:
			return False
		return True

	def helper(root):
		if root:
			if not root.left and (not root.right):
				return root
			if not root.left:
				return helper(root.right)
			if not root.right:
				return helper(root.left)
			root.left = helper(root.left)
			root.right = helper(root.right)
			return root
	root = helper(root)
	return root


def RemoveHalfNodes(root):
	if root is None or isLeaf(root):
		return root
	if root.left is not None and root.right is None:
		return RemoveHalfNodes(root.left)
	if root.right is not None and root.left is None:
		return RemoveHalfNodes(root.right)
	root.left = RemoveHalfNodes(root.left)
	root.right = RemoveHalfNodes(root.right)
	return root

def isLeaf(root):
	return root.left is None and root.right is None


def solve(root):
	if root is None:
		return
	root.left = solve(root.left)
	root.right = solve(root.right)
	if root.left is None and root.right is None:
		return root
	elif root.left is None and root.right:
		return root.right
	elif root.left and root.right is None:
		return root.left
	return root

def RemoveHalfNodes(root):
	return solve(root)


def RemoveHalfNodes(root):
	removeHalfNodesAux(root, root.left, 'left')
	removeHalfNodesAux(root, root.right, 'right')
	return root

def removeHalfNodesAux(parent, node, comingFrom):
	if node is None:
		return
	removeHalfNodesAux(node, node.left, 'left')
	removeHalfNodesAux(node, node.right, 'right')
	if node.left is not None and node.right is None:
		if comingFrom == 'left':
			parent.left = node.left
		elif comingFrom == 'right':
			parent.right = node.left
	if node.left is None and node.right is not None:
		if comingFrom == 'left':
			parent.left = node.right
		elif comingFrom == 'right':
			parent.right = node.right


def RemoveHalfNodes(root):
	if not root:
		return None
	while not root.left and root.right or (root.left and (not root.right)):
		if not root.left:
			root = root.right
		else:
			root = root.left
	root.left = RemoveHalfNodes(root.left)
	root.right = RemoveHalfNodes(root.right)
	return root


def RemoveHalfNodes(root):
	if not root:
		return None
	if not root.left and (not root.right):
		return root
	if not root.left or not root.right:
		return RemoveHalfNodes(root.left or root.right)
	root.left = RemoveHalfNodes(root.left)
	root.right = RemoveHalfNodes(root.right)
	return root


def RemoveHalfNodes(root):
	if root == None:
		return None
	root.left = RemoveHalfNodes(root.left)
	root.right = RemoveHalfNodes(root.right)
	if root.left == None and root.right:
		new = root.right
		del root
		return new
	if root.right == None and root.left:
		new = root.left
		del root
		return new
	return root


def RemoveHalfNodes(A):
	if not A:
		return A
	RemoveHalfNodes(A.left)
	RemoveHalfNodes(A.right)
	if not A.left and A.right:
		A.data = A.right.data
		A.left = A.right.left
		A.right = A.right.right
	if not A.right and A.left:
		A.data = A.left.data
		A.right = A.left.right
		A.left = A.left.left
	return A


def RemoveHalfNodes(root):
	if root == None:
		return None
	root.left = RemoveHalfNodes(root.left)
	root.right = RemoveHalfNodes(root.right)
	if root.left == None and root.right == None:
		return root
	if root.left == None or root.right == None:
		if root.left:
			root_new = root.left
			temp = root
			root = None
			del temp
			return root_new
		else:
			root_new = root.right
			temp = root
			root = None
			del temp
			return root_new
	return root


def RemoveHalfNodes(root):

	def solve(root):
		if root is None:
			return
		if root.left is None and root.right is None:
			return root
		root.left = solve(root.left)
		root.right = solve(root.right)
		if root.left is None and root.right is None:
			return root
		if root.left is None or root.right is None:
			if root.left:
				return root.left
			return root.right
		return root
	return solve(root)


def RemoveHalfNodes(root):
	if not root:
		return None
	root.left = RemoveHalfNodes(root.left)
	root.right = RemoveHalfNodes(root.right)
	if root.left is None and root.right is None:
		return root
	if root.left == None:
		new = root.right
		temp = root
		root = None
		del temp
		return new
	if root.right == None:
		new = root.left
		temp = root
		root = None
		del temp
		return new
	return root
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def printInorder(root):
	if root:
		printInorder(root.left)
		(print(root.data, end=' '),)
		printInorder(root.right)

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		fresh = RemoveHalfNodes(root)
		printInorder(fresh)
		print()


def RemoveHalfNodes(root):

	def solve(root, parent, child):
		if root:
			if root.left and root.right:
				root.left = solve(root.left, root, 'L')
				root.right = solve(root.right, root, 'R')
				return root
			elif root.left:
				if child == 'L':
					parent.left = solve(root.left, parent, 'L')
					return parent.left
				else:
					parent.right = solve(root.left, parent, 'R')
					return parent.right
			elif root.right:
				if child == 'L':
					parent.left = solve(root.right, parent, 'L')
					return parent.left
				else:
					parent.right = solve(root.right, parent, 'R')
					return parent.right
			else:
				return root
		return None
	node = Node(float('inf'))
	node.left = root
	solve(root, node, 'L')
	return node.left
from collections import deque

class Node:

	def __init__(self, val):
		self.right = None
		self.data = val
		self.left = None

def printInorder(root):
	if root:
		printInorder(root.left)
		(print(root.data, end=' '),)
		printInorder(root.right)

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		fresh = RemoveHalfNodes(root)
		printInorder(fresh)
		print()


def RemoveHalfNodes(root):
	if not root:
		return root
	removeHalfNodesUtil(root)
	return root

def removeHalfNodesUtil(root):
	if not root:
		return None
	if not root.left and (not root.right):
		return root
	root.left = removeHalfNodesUtil(root.left)
	root.right = removeHalfNodesUtil(root.right)
	if root.left and root.right:
		return root
	child = root.left if root.left else root.right
	return child


def RemoveHalfNodes(root):

	def helper(node):
		if not node:
			return
		if not node.left and (not node.right):
			return node
		if node.left and node.right:
			node.left = helper(node.left)
			node.right = helper(node.right)
			return node
		if node.right:
			newnode = helper(node.right)
			return newnode
		if node.left:
			newnode = helper(node.left)
			return newnode
	return helper(root)


def RemoveHalfNodes(root):

	def t(root):
		if root is None:
			return None
		if root:
			root.left = t(root.left)
			root.right = t(root.right)
			if root.left is None and root.right is None:
				return root
			if root.left and root.right is None:
				new_root = root.left
				return new_root
			if root.right and root.left is None:
				new_root = root.right
				return new_root
			return root
	t(root)
	return root


def RemoveHalfNodes(root):

	def dfs(node):
		if node == None:
			return None
		node.left = dfs(node.left)
		node.right = dfs(node.right)
		if node.left == None and node.right:
			return node.right
		if node.right == None and node.left:
			return node.left
		return node
	return dfs(root)


def RemoveHalfNodes(root):

	def dfs(node):
		if not node:
			return None
		if not node.left and (not node.right):
			return node
		if not node.left and node.right:
			return dfs(node.right)
		if not node.right and node.left:
			return dfs(node.left)
		else:
			node.left = dfs(node.left)
			node.right = dfs(node.right)
		return node
	return dfs(root)


def RemoveHalfNodes(A):
	if not A:
		return None
	if A.left and A.right:
		A.left = RemoveHalfNodes(A.left)
		A.right = RemoveHalfNodes(A.right)
	elif A.left:
		A.data = A.left.data
		(A.left, A.right) = (A.left.left, A.left.right)
		A = RemoveHalfNodes(A)
	elif A.right:
		A.data = A.right.data
		(A.right, A.left) = (A.right.right, A.right.left)
		A = RemoveHalfNodes(A)
	return A


def RemoveHalfNodes(root):
	if not root:
		return
	lefts = RemoveHalfNodes(root.left)
	rights = RemoveHalfNodes(root.right)
	if lefts and (not rights):
		return lefts
	elif rights and (not lefts):
		return rights
	if root.left:
		root.left = lefts
	if root.right:
		root.right = rights
	return root