Given a Binary Tree of size N, find all the nodes which don't have any sibling. You need to return a list of integers containing all the nodes that don't have a sibling in sorted order.
Note: Root node can not have a sibling so it cannot be included in our answer.
Example 1:
Input :
       37
      /   
    20
    /     
  113 
Output: 20 113
Explanation: 20 and 113 dont have any siblings.
Example 2:
Input :
       1
      / \
     2   3 
Output: -1
Explanation: Every node has a sibling.
Your Task:  
You dont need to read input or print anything. Complete the function noSibling() which takes the root of the tree as input parameter and returns a list of integers containing all the nodes that don't have a sibling in sorted order. If all nodes have a sibling, then the returning list should contain only one element -1.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(Height of the tree)
Constraints:
1 ≤ N ≤ 10^4
All nodes have distinct values.

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3

'''
class Node:
    def __init__(self, val):
        self.right = None
        self.data = val
        self.left = None
'''
def noSibling(root):
    # code here


Solutions:
def check(root, x):
	if root is None:
		return
	if root.left is None and root.right is not None:
		x.append(root.right.data)
	elif root.left is not None and root.right is None:
		x.append(root.left.data)
	check(root.left, x)
	check(root.right, x)

def noSibling(root):
	x = []
	check(root, x)
	if x:
		x.sort()
		return x
	return [-1]


def noSibling(root):
	res = []

	def t(rt, re):
		if rt is None:
			return
		if rt.left is None and rt.right is not None:
			re.append(rt.right.data)
		elif rt.left is not None and rt.right is None:
			re.append(rt.left.data)
		t(rt.left, re)
		t(rt.right, re)
	t(root, res)
	if res:
		res.sort()
		return res
	else:
		return [-1]


def noSibling(root):
	q = []
	ans = []
	if not root:
		return []
	q.append(root)
	while len(q) != 0:
		n = len(q)
		for i in range(n):
			node = q.pop(0)
			if node.left and (not node.right):
				ans.append(node.left.data)
				q.append(node.left)
			if node.right and (not node.left):
				ans.append(node.right.data)
				q.append(node.right)
			if node.left and node.right:
				q.append(node.left)
				q.append(node.right)
	if len(ans) == 0:
		return [-1]
	ans.sort()
	return ans


def noSibling(root):
	queue = [root]
	ans = []
	while queue:
		node = queue.pop(0)
		if node.left:
			queue.append(node.left)
		if node.right:
			queue.append(node.right)
		if not node.left and node.right:
			ans.append(node.right.data)
		if node.left and (not node.right):
			ans.append(node.left.data)
	return list(sorted(ans)) if ans else [-1]


from collections import deque

def noSibling(root):
	queue = deque()
	siblings = []
	queue.append(root)
	while queue:
		size = len(queue)
		for _ in range(size):
			node = queue.popleft()
			if node.left and node.right:
				queue.append(node.left)
				queue.append(node.right)
			elif node.left:
				queue.append(node.left)
				siblings.append(node.left.data)
			elif node.right:
				queue.append(node.right)
				siblings.append(node.right.data)
	return sorted(siblings) if len(siblings) > 0 else [-1]


def noSiblingHelper(root, mylist):
	if root is None:
		return -1
	if root.left is not None and root.right is not None:
		noSiblingHelper(root.left, mylist)
		noSiblingHelper(root.right, mylist)
	elif root.left is not None and root.right is None:
		mylist.append(root.left.data)
		noSiblingHelper(root.left, mylist)
	elif root.left is None and root.right is not None:
		mylist.append(root.right.data)
		noSiblingHelper(root.right, mylist)
	if len(mylist) < 1:
		return -1
	return mylist

def noSibling(root):
	mylist = []
	ans = noSiblingHelper(root, mylist)
	x = []
	if ans == -1:
		x.append(-1)
		return x
	ans.sort()
	return ans


def noSibling(root):
	out = []

	def traverse(root):
		if not root:
			return
		if root.left and (not root.right):
			out.append(root.left.data)
		if not root.left and root.right:
			out.append(root.right.data)
		traverse(root.left)
		traverse(root.right)
	traverse(root)
	return sorted(out) if out != [] else [-1]


def noSibling(root):
	l = []

	def fun(root, l):
		if root is None:
			return
		if root.left is None and root.right is None:
			return
		if root.left is None and root.right is not None:
			l.append(root.right.data)
			fun(root.right, l)
		elif root.right is None and root.left is not None:
			l.append(root.left.data)
			fun(root.left, l)
		elif root.left is not None and root.right is not None:
			fun(root.left, l)
			fun(root.right, l)
		return l
	fun(root, l)
	if len(l) == 0:
		return [-1]
	return sorted(l)


def noSibling(root):
	r = find(root, [])
	if r == []:
		return [-1]
	r.sort()
	return r

def find(root, res):
	if root == None:
		return res
	if root.left == None and root.right != None:
		res.append(root.right.data)
	if root.left != None and root.right == None:
		res.append(root.left.data)
	find(root.left, res)
	find(root.right, res)
	return res


def noSibling(root):
	ans = []

	def preorder(root, ans):
		if root is None:
			return
		if root.left and root.right == None:
			ans.append(root.left.data)
		if root.right and root.left == None:
			ans.append(root.right.data)
		preorder(root.left, ans)
		preorder(root.right, ans)
	ans = []
	preorder(root, ans)
	ans.sort()
	if len(ans) == 0:
		return [-1]
	return ans


def noSibling(root):
	ans = []

	def pre(root):
		if not root:
			return
		if root.right and (not root.left):
			ans.append(root.right.data)
		if not root.right and root.left:
			ans.append(root.left.data)
		pre(root.left)
		pre(root.right)
	pre(root)
	if len(ans) > 0:
		return sorted(ans)
	else:
		return [-1]


def noSibling(root):

	def onlychild(root, v):
		if root is None:
			return
		onlychild(root.left, v)
		if root.left is None and root.right is not None:
			v.append(root.right.data)
		if root.left is not None and root.right is None:
			v.append(root.left.data)
		onlychild(root.right, v)
	v = []
	onlychild(root, v)
	v.sort()
	return v if len(v) > 0 else [-1]


def noSibling(root):
	List = []

	def Transverse(root):
		if root == None:
			return
		if root.left == None and root.right != None:
			List.append(root.right.data)
		if root.left != None and root.right == None:
			List.append(root.left.data)
		Transverse(root.left)
		Transverse(root.right)
	Transverse(root)
	if List == []:
		return [-1]
	else:
		List.sort()
		return List


def noSibling(root):
	ans = []
	if root == None:
		return [-1]
	queue = []
	queue.append(root)
	while len(queue) != 0:
		temp = queue.pop(0)
		if temp.left != None and temp.right == None:
			ans.append(temp.left.data)
		if temp.right != None and temp.left == None:
			ans.append(temp.right.data)
		if temp.left != None:
			queue.append(temp.left)
		if temp.right != None:
			queue.append(temp.right)
	if len(ans) == 0:
		return [-1]
	ans.sort()
	return ans


def fun(root, l):
	if root == None:
		return
	elif root.left == None and root.right != None:
		l.append(root.right.data)
	elif root.left != None and root.right == None:
		l.append(root.left.data)
	fun(root.left, l)
	fun(root.right, l)

def noSibling(root):
	l = []
	fun(root, l)
	if len(l) == 0:
		l.append(-1)
	else:
		l.sort()
	return l


def noSiblingUtil(root):
	global ans
	if root is None:
		return
	elif root.right is None and root.left is None:
		return
	elif root.left is None:
		ans.append(root.right.data)
		noSiblingUtil(root.right)
	elif root.right is None:
		ans.append(root.left.data)
		noSiblingUtil(root.left)
	else:
		noSiblingUtil(root.left)
		noSiblingUtil(root.right)
	return

def noSibling(root):
	global ans
	ans = []
	ans.clear()
	noSiblingUtil(root)
	if len(ans) == 0:
		ans.append(-1)
	ans.sort()
	return ans


def noSibling(root):

	def no(root, l):
		if root == None:
			return l
		no(root.left, l)
		if root.left != None and root.right == None:
			l.append(root.left.data)
		if root.right != None and root.left == None:
			l.append(root.right.data)
		no(root.right, l)
	l = []
	no(root, l)
	l.sort()
	if len(l) == 0:
		return [-1]
	return l


def paths(root, ans):
	if not root:
		return
	if root.left and (not root.right):
		ans.append(root.left.data)
	if not root.left and root.right:
		ans.append(root.right.data)
	paths(root.left, ans)
	paths(root.right, ans)
	return

def noSibling(root):
	ans = []
	paths(root, ans)
	if ans == []:
		return [-1]
	ans.sort()
	return ans


def noSibling(root):
	res = []

	def helper(root):
		if root == None:
			return
		if root.left != None and root.right == None:
			res.append(root.left.data)
		if root.right != None and root.left == None:
			res.append(root.right.data)
		helper(root.left)
		helper(root.right)
	helper(root)
	res.sort()
	return res if len(res) > 0 else [-1]


def noSibling(root):
	l = []

	def s(root):
		if root:
			if root.left and (not root.right):
				l.append(root.left.data)
			if not root.left and root.right:
				l.append(root.right.data)
			if root.left:
				s(root.left)
			if root.right:
				s(root.right)
	s(root.left)
	s(root.right)
	l.sort()
	if l:
		return l
	return [-1]
	return []


def get(root, li):
	if not root:
		return
	if root.left and root.right:
		pass
	elif root.left:
		li.append(root.left.data)
	elif root.right:
		li.append(root.right.data)
	get(root.left, li)
	get(root.right, li)

def noSibling(root):
	li = []
	get(root, li)
	if len(li) == 0:
		return [-1]
	else:
		li.sort()
		return li


def noSibling(root):
	res = []

	def dfs(node):
		if not node:
			return
		if node.left and (not node.right):
			res.append(node.left.data)
		elif node.right and (not node.left):
			res.append(node.right.data)
		dfs(node.left)
		dfs(node.right)
	dfs(root)
	res.sort()
	if res:
		return res
	return [-1]


def noSibling(root):
	l = []
	if not root:
		return [-1]
	if root.left and root.right:
		l += noSibling(root.left)
		l += noSibling(root.right)
	elif root.left and (not root.right):
		l.append(root.left.data)
		l += noSibling(root.left)
	elif root.right and (not root.left):
		l.append(root.right.data)
		l += noSibling(root.right)
	if not l:
		return [-1]
	else:
		l.sort()
		for i in l:
			if i == -1:
				l.remove(-1)
		return l


def noSibling(root):
	if root is None:
		return []
	(queue, a, k) = ([root], [], 0)
	while len(queue) > 0:
		k = len(queue)
		for _ in range(k):
			s = queue[0]
			if s.left and (not s.right):
				a.append(s.left.data)
				queue.append(s.left)
			if s.right and (not s.left):
				a.append(s.right.data)
				queue.append(s.right)
			if s.left and s.right:
				queue.append(s.left)
				queue.append(s.right)
			queue.pop(0)
	if len(a) == 0:
		return [-1]
	a.sort()
	return a


def solve(root, lis):
	if root == None:
		return
	if root.left != None and root.right == None:
		lis.append(root.left.data)
	if root.left == None and root.right != None:
		lis.append(root.right.data)
	solve(root.left, lis)
	solve(root.right, lis)

def noSibling(root):
	lis = []
	k = root
	solve(root, lis)
	if not lis:
		return [-1]
	lis.sort()
	return lis


def noSibling(root):
	q = [root]
	res = []
	while q:
		k = q.pop(0)
		if k.left and (not k.right):
			res.append(k.left.data)
		if not k.left and k.right:
			res.append(k.right.data)
		if k.right:
			q.append(k.right)
		if k.left:
			q.append(k.left)
	if not res:
		return [-1]
	res.sort()
	return res


def noSibling(root):
	q = [root]
	res = []
	while q:
		l = len(q)
		for i in range(l):
			k = q.pop()
			if k.left and (not k.right):
				res.append(k.left.data)
			if not k.left and k.right:
				res.append(k.right.data)
			if k.right:
				q.append(k.right)
			if k.left:
				q.append(k.left)
	if not res:
		return [-1]
	res.sort()
	return res


def noSibling(root):
	ans = []

	def help(root):
		if root == None:
			return
		if root.left and (not root.right):
			ans.append(root.left.data)
		if root.right and (not root.left):
			ans.append(root.right.data)
		help(root.left)
		help(root.right)
	help(root)
	return sorted(ans) if ans else [-1]


def noSibling(root):
	ns = []

	def trav(r):
		if r.left is not None:
			if r.right is None:
				ns.append(r.left.data)
				trav(r.left)
			else:
				trav(r.left)
		if r.right is not None:
			if r.left is None:
				ns.append(r.right.data)
				trav(r.right)
			else:
				trav(r.right)
	trav(root)
	if len(ns) == 0:
		return [-1]
	return sorted(ns)