Given a Binary Tree, print the diagonal traversal of the binary tree.
Consider lines of slope -1 passing between nodes. Given a Binary Tree, print all diagonal elements in a binary tree belonging to same line.
If the diagonal element are present in two different subtress then left subtree diagonal element should be taken first and then right subtree. 
Example 1:
Input :
            8
         /     \
        3      10
      /   \      \
     1     6     14
         /   \   /
        4     7 13
Output : 8 10 14 3 6 7 13 1 4
Explanation:
Diagonal Traversal of binary tree : 
 8 10 14 3 6 7 13 1 4
Your Task:
You don't need to read input or print anything. The task is to complete the function diagonal() that takes the root node as input argumets and returns the diagonal traversal of the given tree.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Here N is number of nodes.
Constraints:
1 <= Number of nodes<= 10^{5}
1 <= Data of a node<= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

# Node Class:

class Node:

    def _init_(self,val):

        self.data = val

        self.left = None

        self.right = None

'''

#Complete the function below

class Solution:

    def diagonal(self,root):

        #:param root: root of the given tree.

        #return: print out the diagonal traversal,  no need to print new line

        #code here







Solutions:
class Solution:

	def diagonal(self, root):
		if root is None:
			return
		out = []
		node = root
		left_q = deque()
		while node:
			out.append(node.data)
			if node.left:
				left_q.appendleft(node.left)
			if node.right:
				node = node.right
			elif len(left_q) >= 1:
				node = left_q.pop()
			else:
				node = None
		return out


class Solution:

	def diagonal(self, root):
		q = []
		ans = []
		q.append(root)
		while q:
			a = q.pop(0)
			ans.append(a.data)
			if a.left:
				q.append(a.left)
			while a.right:
				ans.append(a.right.data)
				if a.right.left:
					q.append(a.right.left)
				a = a.right
		return ans


from collections import defaultdict

class Solution:

	def diagonal(self, root):
		ans = []
		d = defaultdict(list)

		def solve(root, l):
			if root.left == None and root.right == None:
				d[l].append(root.data)
				return
			if root.left:
				solve(root.left, l - 1)
			d[l].append(root.data)
			if root.right:
				solve(root.right, l)
		if root == None:
			return []
		solve(root, 0)
		l = []
		for i in d.keys():
			l.append(i)
		l.sort(reverse=-1)
		for i in l:
			ans.extend(d[i])
		return ans


from collections import deque

class Solution:

	def diagonal(self, root):
		q = deque()
		q.append(root)
		ans = []
		while q:
			x = q.popleft()
			while x is not None:
				if x.left:
					q.append(x.left)
				ans.append(x.data)
				x = x.right
		return ans


class Solution:

	def diagonal(self, root):
		vis = []
		n = root
		q = deque()
		while n:
			vis.append(n.data)
			if n.left:
				q.appendleft(n.left)
			if n.right:
				n = n.right
			elif len(q) >= 1:
				n = q.pop()
			else:
				n = None
		return vis


class Solution:

	def diagonal(self, root):
		res = []
		q = []
		q.append(root)

		def traverse(node):
			if node != None:
				res.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					traverse(node.right)
		while q != []:
			x = q.pop(0)
			traverse(x)
		return res


from collections import defaultdict

class Solution:

	def diagonal(self, root):
		d = defaultdict(list)

		def sol(root, i):
			if root.left == None and root.right == None:
				d[i].append(root.data)
				return
			d[i].append(root.data)
			if root.left:
				left = sol(root.left, i - 1)
			if root.right:
				right = sol(root.right, i)
		sol(root, 0)
		r = []
		for j in sorted(d.keys(), reverse=True):
			r.extend(d[j])
		return r


class Solution:

	def diagonal(self, root):

		def dig(root):
			if root is None:
				return []
			l1 = []
			q = []
			q = [root]
			while q:
				node = q.pop(0)
				while node:
					l1.append(node.data)
					if node.left:
						q.append(node.left)
					node = node.right
			return l1
		return dig(root)


from collections import defaultdict

class Solution:

	def diagonal(self, root):
		d = defaultdict(list)

		def solve(root, idx):
			if root.left == None and root.right == None:
				d[idx].append(root.data)
				return
			d[idx].append(root.data)
			if root.left:
				left = solve(root.left, idx - 1)
			if root.right:
				right = solve(root.right, idx)
		solve(root, 0)
		res = []
		for i in sorted(d.keys(), reverse=True):
			res.extend(d[i])
		return res


class Solution:

	def diagonal(self, root):
		d = {}

		def traverse(root, tag):
			if root != []:
				if tag in d:
					d[tag].append(root.data)
				else:
					d[tag] = [root.data]
				if root.left:
					traverse(root.left, tag - 1)
				if root.right:
					traverse(root.right, tag)
		traverse(root, 0)
		k = sorted(d.items(), key=lambda x: -x[0])
		ans = []
		for (i, j) in k:
			ans.extend(j)
		return ans


class Solution:

	def diagonal(self, root):
		diagonal_map = {}
		diagonal_traversal_helper(root, 0, diagonal_map)
		result = []
		for level in diagonal_map:
			result.extend(diagonal_map[level])
		return result

def diagonal_traversal_helper(node, level, diagonal_map):
	if node is None:
		return
	if level in diagonal_map:
		diagonal_map[level].append(node.data)
	else:
		diagonal_map[level] = [node.data]
	diagonal_traversal_helper(node.left, level + 1, diagonal_map)
	diagonal_traversal_helper(node.right, level, diagonal_map)


class Solution:

	def diagonal(self, root):
		q = []
		a = []
		if root == None:
			return
		q.append(root)
		while len(q) != 0:
			n = q[0]
			q.pop(0)
			while n:
				if n.left:
					q.append(n.left)
				a.append(n.data)
				n = n.right
		return a


from collections import defaultdict

class Solution:

	def diagonal(self, root):
		ans = []
		d = defaultdict(list)

		def dfs(x, l):
			d[l].append(x.data)
			if x.left:
				dfs(x.left, l + 1)
			if x.right:
				dfs(x.right, l)
		dfs(root, 0)
		ans = []
		for x in d:
			ans.extend(d[x])
		return ans


class Solution:

	def diagonal(self, root):
		if root == None:
			return []
		q = [root]
		tmp = []
		ans = []
		while q:
			nod = q.pop(0)
			while nod:
				ans.append(nod.data)
				if nod.left:
					tmp.append(nod.left)
				nod = nod.right
			if len(q) == 0:
				while tmp:
					q.append(tmp.pop(0))
		return ans


class Solution:

	def diagonal(self, root):
		q = deque()
		q.append(root)
		ans = []
		while len(q) >= 1:
			x = q.popleft()
			while x is not None:
				if x.left is not None:
					q.append(x.left)
				ans.append(x.data)
				x = x.right
		return ans


class Solution:

	def util(self, root, a):
		global d
		if root == None:
			return
		if d.get(a) == None:
			d[a] = [root.data]
		else:
			d[a].append(root.data)
		self.util(root.left, a - 1)
		self.util(root.right, a)

	def diagonal(self, root):
		global d
		d = {}
		self.util(root, 0)
		ans = []
		for (k, v) in sorted(d.items(), reverse=True):
			for i in v:
				ans.append(i)
		return ans


from collections import deque

class Solution:

	def diagonal(self, root):
		queue = deque()
		ans = []
		queue.append(root)
		if root is None:
			return ans
		while queue:
			temp = queue.popleft()
			while temp:
				if temp.left:
					queue.append(temp.left)
				ans.append(temp.data)
				temp = temp.right
		return ans


from collections import deque

class Solution:

	def diagonal(self, root):
		hashmap = {}

		def solve(root, index):
			if root is None:
				return
			if index in hashmap:
				hashmap[index].append(root.data)
			else:
				hashmap[index] = [root.data]
			if root.left is not None:
				solve(root.left, index + 1)
			if root.right is not None:
				solve(root.right, index)
		solve(root, 0)
		ans = []
		for i in sorted(hashmap.keys()):
			ans += hashmap[i]
		return ans


class Solution:

	def diagonal(self, root):
		q = []
		res = []
		q.append(root)
		while len(q) > 0:
			p = q.pop(0)
			res.append(p.data)
			while p:
				if p.right != None:
					res.append(p.right.data)
				if p.left != None:
					q.append(p.left)
				p = p.right
		return res


from collections import defaultdict

class Solution:

	def diagonal(self, root):
		ans = []
		queue = [root]
		while queue:
			node = queue.pop(0)
			while node:
				ans.append(node.data)
				if node.left:
					queue.append(node.left)
				if node.right:
					node = node.right
				else:
					break
		return ans


class Solution:

	def diagonal(self, root):
		if root == None:
			return []
		queue = []
		queue.append(root)
		ans = []
		while queue:
			temp = queue.pop(0)
			while temp:
				ans.append(temp.data)
				if temp.left != None:
					queue.append(temp.left)
				if temp.right:
					temp = temp.right
				else:
					break
		return ans


class Solution:

	def diagonal(self, root):
		result = list()
		node = root
		left_q = deque()
		while node:
			result.append(node.data)
			if node.left:
				left_q.appendleft(node.left)
			if node.right:
				node = node.right
			else:
				node = left_q.pop() if len(left_q) >= 1 else None
		return result


from collections import deque

class Solution:

	def diagonal(self, root):
		res = []
		q = deque()
		q.append(root)
		while len(q):
			p = q.popleft()
			res.append(p.data)
			while p:
				if p.left:
					q.append(p.left)
				if p.right:
					res.append(p.right.data)
				p = p.right
		return res


from collections import *

class Solution:

	def __init__(self):
		self.d = {}

	def diagonal(self, root):
		q = deque()
		q.append([root, 0, 0])
		while q:
			(v, x, y) = q.pop()
			if y - x in self.d:
				self.d[y - x].append(v.data)
			else:
				self.d[y - x] = [v.data]
			if v.right:
				q.append([v.right, x + 1, y + 1])
			if v.left:
				q.append([v.left, x - 1, y + 1])
		answer = []
		for i in sorted(self.d):
			answer.extend(self.d[i])
		return answer


from queue import Queue

class Solution:

	def diagonal(self, root):
		q = [root]
		while q:
			x = q.pop(0)
			while x:
				print(x.data, end=' ')
				if x.left:
					q.append(x.left)
				x = x.right
		return []


class Solution:

	def diagonal(self, root):

		def diagnolView(root, dict, level):
			if root is None:
				return
			if level not in dict:
				dict[level] = [root.data]
			else:
				dict[level].append(root.data)
			diagnolView(root.left, dict, level + 1)
			diagnolView(root.right, dict, level)
		dict = {}
		diagnolView(root, dict, 0)
		arr = []
		for i in dict:
			arr += dict[i]
		return arr


class Solution:

	def rec_sol(self, root, d, save_dict):
		try:
			save_dict[d].append(root.data)
		except:
			save_dict[d] = [root.data]
		if root.left != None:
			self.rec_sol(root.left, d + 1, save_dict)
		if root.right != None:
			self.rec_sol(root.right, d, save_dict)
		return

	def diagonal(self, root):
		save_dict = {}
		self.rec_sol(root, 0, save_dict)
		final = []
		for i in save_dict:
			for el in save_dict[i]:
				final.append(el)
		return final


class Solution:

	def diagonal(self, root):
		s = []
		ans = []
		s.append(root)
		while len(s) != 0:
			size = len(s)
			while size != 0:
				rn = s.pop(0)
				while rn != None:
					ans.append(rn.data)
					if rn.left != None:
						s.append(rn.left)
					rn = rn.right
				size -= 1
		return ans


class Solution:

	def diagonal(self, root):
		queue = []
		l = []
		queue.append(root)
		while len(queue) > 0:
			temp = queue.pop(0)
			while temp:
				if temp.left:
					queue.append(temp.left)
				l.append(temp.data)
				temp = temp.right
		return l


class Solution:

	def diagonal(self, root):
		q = deque([root])
		res = []
		while q:
			temp = q.popleft()
			while temp:
				res.append(temp.data)
				if temp.left:
					q.append(temp.left)
				temp = temp.right
		return res


class Solution:

	def diagonal(self, root):
		ans = []
		q = deque([])
		q.append(root)
		while q:
			n = len(q)
			for _ in range(len(q)):
				d = q.popleft()
				ans.append(d.data)
				if d.left:
					q.append(d.left)
				while d.right:
					d = d.right
					ans.append(d.data)
					if d.left:
						q.append(d.left)
		return ans


class Solution:

	def diagonal(self, root):

		def helper(root, dic, diagonal):
			if root == None:
				return
			if diagonal in dic:
				dic[diagonal].append(root.data)
			else:
				dic[diagonal] = [root.data]
			helper(root.left, dic, diagonal + 1)
			helper(root.right, dic, diagonal)
			return dic
		if not root:
			return
		dic = {}
		dic = helper(root, dic, 0)
		l = list(dic.keys())
		l.sort()
		res = []
		for k in l:
			res += dic[k]
		return res


from queue import LifoQueue
from collections import defaultdict

def pre_order(root, level, diagonals):
	diagonals[level].append(root.data)
	if root.left:
		pre_order(root.left, level + 1, diagonals)
	if root.right:
		pre_order(root.right, level, diagonals)

class Solution:

	def diagonal(self, root):
		diagonals_map = defaultdict(list)
		output = []
		pre_order(root, 0, diagonals_map)
		for level in diagonals_map:
			output.extend(diagonals_map[level])
		return output


class Solution:

	def diagonal(self, root):
		if not root:
			return []
		q = [root]
		res = []
		while q:
			curr = q.pop(0)
			while curr:
				res.append(curr.data)
				if curr.left:
					q.append(curr.left)
				curr = curr.right
		return res


class Solution:

	def diagonal(self, root):

		def find(root, dig, dict):
			if root is None:
				return
			if dig not in dict:
				dict[dig] = []
			dict[dig].append(root.data)
			find(root.left, dig + 1, dict)
			find(root.right, dig, dict)
		ans = []
		dict = {}
		find(root, 0, dict)
		for dig in dict:
			for num in dict[dig]:
				ans.append(num)
		return ans


class Solution:

	def diagonal(self, root):
		if not root:
			return []
		q = deque([root])
		res = []
		while q:
			for i in range(len(q)):
				curr = q.popleft()
				while curr:
					res.append(curr.data)
					if curr.left:
						q.append(curr.left)
					curr = curr.right
		return res


class Solution:

	def diagonal(self, root):
		if root == None:
			return []
		ans = []
		q = []
		q.append(root)
		while len(q) != 0:
			s = len(q)
			while s != 0:
				curr = q.pop(0)
				while curr != None:
					ans.append(curr.data)
					if curr.left != None:
						q.append(curr.left)
					if curr.right != None:
						curr = curr.right
					else:
						break
				s -= 1
		return ans


from collections import deque

class Solution:

	def diagonal(self, root):
		q = deque()
		q.append(root)
		ans = []
		while q:
			curr = q.popleft()
			while curr:
				ans.append(curr.data)
				if curr.left:
					q.append(curr.left)
				curr = curr.right
		return ans


class Solution:

	def diagonal(self, root):
		l = []
		queue = [root]
		while len(queue) > 0:
			s = len(queue)
			while s > 0:
				node = queue.pop(0)
				while node != None:
					l.append(node.data)
					if node.left:
						queue.append(node.left)
					node = node.right
				s -= 1
		return l


class Solution:

	def diagonal(self, root):
		ans = []
		Q = [root]
		s = 1
		while Q != []:
			m = 0
			while s:
				a = Q.pop(0)
				while a:
					if a.left:
						Q.append(a.left)
						m += 1
					ans.append(a.data)
					a = a.right
				s -= 1
			s = m
		return ans


class Solution:

	def diagonal(self, root):
		q = [root]
		ans = []
		while q:
			l = len(q)
			for i in range(l):
				root = q.pop(0)
				temp = root
				while temp:
					ans.append(temp.data)
					if temp.left:
						q.append(temp.left)
					temp = temp.right
		return ans


class Solution:

	def diagonal(self, root):
		q = []
		ans = []
		if root is None:
			return ans
		q.append(root)
		while q:
			temp = q.pop(0)
			while temp:
				if temp.left:
					q.append(temp.left)
				ans.append(temp.data)
				temp = temp.right
		return ans


class Solution:

	def diagonal(self, root):
		arr = [root]
		ans = []
		while len(arr) > 0:
			temp = arr.pop(0)
			while temp is not None:
				if temp.left:
					arr.append(temp.left)
				ans.append(temp.data)
				temp = temp.right
		return ans


class Solution:

	def diagonal(self, root):
		q = [root]
		(temp, res) = ([], [])
		while q:
			node = q.pop(0)
			res.append(node.data)
			if node.left:
				temp.append(node.left)
			if node.right:
				q.append(node.right)
			if not q and temp:
				q.append(temp.pop(0))
		return res


class Solution:

	def diagonal(self, root):
		if not root:
			return
		(queue, result) = ([], [])
		queue.append(root)
		while len(queue) > 0:
			n = len(queue)
			ans = []
			while n > 0:
				temp = queue[0]
				queue.pop(0)
				while temp is not None:
					ans.append(temp.data)
					if temp.left is not None:
						queue.append(temp.left)
					temp = temp.right
				n -= 1
			result.append(' '.join(map(str, ans)))
		return result


from collections import defaultdict

class Solution:

	def diagonal(self, root):
		if root is None:
			return []
		dict1 = defaultdict(list)
		q = [(root, 0)]
		while len(q):
			for i in range(len(q)):
				(s, d) = q.pop()
				if s.right:
					q.append((s.right, d))
				if s.left:
					q.append((s.left, d + 1))
				dict1[d].append(s.data)
		res = []
		for i in sorted(dict1):
			res.extend(dict1[i])
		return res


class Solution:

	def diagonal(self, root):
		if not root:
			return []
		ans = []
		q = [root]
		while len(q) > 0:
			node = q.pop(0)
			while node:
				if node.left:
					q.append(node.left)
				ans.append(node.data)
				node = node.right
		return ans


class Solution:

	def diagonal(self, root):
		queue = []
		queue.append(root)
		ans = []

		def dfs(root):
			if root == None:
				return
			ans.append(root.data)
			if root.left:
				queue.append(root.left)
			if root.right:
				dfs(root.right)
		while len(queue) != 0:
			root = queue.pop(0)
			dfs(root)
		return ans


from collections import deque

class Solution:

	def diagonal(self, root):
		ans = []
		q = deque()
		new_node = Node(0)
		new_node.left = root
		q.append(new_node)
		while len(q) > 0:
			node = q.popleft()
			node = node.left
			while node is not None:
				ans.append(node.data)
				if node.left is not None:
					q.append(node)
				node = node.right
		return ans


from collections import deque

class Solution:

	def diagonal(self, root):
		q = deque()
		if root is None:
			return []
		q.appendleft(root)
		res = []
		while len(q) > 0:
			t = q.pop()
			while t is not None:
				res.append(t.data)
				if t.left is not None:
					q.appendleft(t.left)
				t = t.right
		return res


class Solution:

	def diagonal(self, root):
		queue = []
		ans = []
		queue.append(root)
		while queue:
			curr = queue.pop(0)
			while curr:
				if curr.left:
					queue.append(curr.left)
				ans.append(curr.data)
				curr = curr.right
		return ans


class Solution:

	def diagonal(self, root):
		result = []
		if root == None:
			return result
		q = deque()
		q.append(root)
		while len(q) != 0:
			current = q.popleft()
			while current:
				result.append(current.data)
				if current.left:
					q.append(current.left)
				current = current.right
		return result


import collections

class Solution:

	def diagonal(self, root):
		res = []
		q = collections.deque()
		q.append(root)
		while q:
			a = q.popleft()
			res.append(a.data)
			if a.left:
				q.append(a.left)
			t = a.right
			if t:
				res.append(t.data)
			while t:
				if t.left:
					q.append(t.left)
				if t.right:
					res.append(t.right.data)
				t = t.right
		return res


class Solution:

	def diagonal(self, root):

		def diag(root, x, d):
			if root is None:
				return
			try:
				d[x].append(root.data)
			except KeyError:
				d[x] = [root.data]
			diag(root.left, x + 1, d)
			diag(root.right, x, d)
		d = dict()
		a = []
		diag(root, 0, d)
		for i in d:
			for j in d[i]:
				a.append(j)
		return a


import collections

class Solution:

	def dfs(self, node):
		if not node:
			return
		self.diag_lst.append(node.data)
		if node.left:
			self.q.append(node.left)
		self.dfs(node.right)
		return

	def diagonal(self, root):
		self.q = collections.deque()
		self.diag_lst = []
		self.q.append(root)
		while self.q:
			self.dfs(self.q.popleft())
		return self.diag_lst


class Solution:

	def diagonal(self, root):
		right = []
		res = []
		q = [root]
		while q or right:
			if q:
				x = q.pop(0)
			else:
				x = right.pop(0)
			if x.right:
				q.append(x.right)
			if x.left:
				right.append(x.left)
			res.append(x)
		for i in range(len(res)):
			res[i] = res[i].data
		return res


class Solution:

	def diagonal(self, root):
		temp = []
		result = []

		def trav(root):
			if root == None:
				return
			result.append(root.data)
			if root.left != None:
				temp.append(root.left)
			if root.right == None:
				if len(temp) == 0:
					return
				x = temp.pop(0)
				trav(x)
			else:
				trav(root.right)
		trav(root)
		return result


class Solution:

	def diagonal(self, root):
		if root is None:
			return
		level = []
		ansArr = []
		while root:
			ansArr.append(root.data)
			if root.left:
				level.append(root.left)
			if root.right:
				root = root.right
			else:
				if not level:
					break
				root = level.pop(0)
		return ansArr


class Solution:

	def diagonal(self, root):
		q = deque()
		q.append(root)
		ans = []
		while len(q) > 0:
			curr = q.popleft()
			while curr is not None:
				ans.append(curr.data)
				if curr.left is not None:
					q.append(curr.left)
				curr = curr.right
		return ans


class Solution:

	def diagonal(self, root):
		ans = []
		if root is None:
			return ans
		import collections
		queue = collections.deque()
		queue.append(root)
		while len(queue) != 0:
			curr = queue.popleft()
			while curr is not None:
				ans.append(curr.data)
				if curr.left != None:
					queue.append(curr.left)
				curr = curr.right
		return ans


class Solution:

	def diagonal(self, root):
		traverse_queue = [root]
		final_result = []
		while len(traverse_queue) > 0:
			node_pop = traverse_queue.pop(0)
			final_result.append(node_pop.data)
			curr = node_pop
			while curr is not None:
				if curr.left is not None:
					traverse_queue.append(curr.left)
				curr = curr.right
				if curr is not None:
					final_result.append(curr.data)
		return final_result