Given a Binary Tree. Find the Zig-Zag Level Order Traversal of the Binary Tree.
 
Example 1:
Input:
        1
      /   \
     2     3
    / \   /  \
   4   5 6    7
Output:
1 3 2 4 5 6 7
Example 2:
Input:
           7
        /     \
       9       7
     /  \     /   
    8    8   6     
   /  \
  10   9 
Output:
7 7 9 8 8 6 9 10 
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function zigZagTraversal() which takes the root node of the Binary Tree as its input and returns a list containing the node values as they appear in the Zig-Zag Level-Order Traversal of the Tree.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
 
Constraints:
1 <= N <= 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self,val):

        self.data = val

        self.left = None

        self.right = None

'''



class Solution:

    #Function to store the zig zag order traversal of tree in a list.

    def zigZagTraversal(self, root):

        Add# Your code here

Solutions:
class Solution:

	def zigZagTraversal(self, root):
		ret = []
		level = [root]
		i = 1
		while root and level:
			currentnodes = []
			nextlevel = []
			for node in level:
				currentnodes.append(node.data)
				if node.left:
					nextlevel.append(node.left)
				if node.right:
					nextlevel.append(node.right)
			if i % 2 == 1:
				ret.append(currentnodes)
			else:
				currentnodes.reverse()
				ret.append(currentnodes)
			i = i + 1
			level = nextlevel
		retfl = []
		[retfl.extend(sublist) for sublist in ret]
		return retfl


class Solution:

	def zigZagTraversal(self, root):
		if root == None:
			return []
		ans = []
		s1 = []
		s2 = []
		s1.append(root)
		while s1 != [] or s2 != []:
			while s1 != []:
				t = s1.pop()
				ans.append(t.data)
				if t.left != None:
					s2.append(t.left)
				if t.right != None:
					s2.append(t.right)
			while s2 != []:
				t2 = s2.pop()
				ans.append(t2.data)
				if t2.right != None:
					s1.append(t2.right)
				if t2.left != None:
					s1.append(t2.left)
		return ans


class Solution:

	def zigZagTraversal(self, root):
		result = []
		if root == None:
			return result
		q = deque()
		q.append(root)
		leftToRight = True
		while len(q) != 0:
			size = len(q)
			row = [0] * size
			for i in range(size):
				node = q.popleft()
				index = i if leftToRight else size - i - 1
				row[index] = node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			leftToRight = not leftToRight
			result += row
		return result


class Solution:

	def zigZagTraversal(self, root):
		if not root:
			return []
		curr = [root]
		ans = []
		while curr:
			new_curr = []
			temp = []
			for node in curr:
				temp.append(node.data)
				if node.left:
					new_curr.append(node.left)
				if node.right:
					new_curr.append(node.right)
			ans.append(temp)
			curr = new_curr
		final_ans = []
		for (i, a) in enumerate(ans):
			if i % 2 == 0:
				for num in a:
					final_ans.append(num)
			else:
				for num in reversed(a):
					final_ans.append(num)
		return final_ans


from collections import deque

class Solution:

	def zigZagTraversal(self, root):
		if not root:
			return []
		i = 0
		ans = []
		q = deque([root])
		while q:
			a = []
			for x in q:
				a.append(x.data)
			if i % 2 == 0:
				ans.extend(a)
			else:
				ans.extend(a[::-1])
			for _ in range(len(q)):
				x = q.popleft()
				if x.left:
					q.append(x.left)
				if x.right:
					q.append(x.right)
			i += 1
		return ans


class Solution:

	def zigZagTraversal(self, root):
		if root == None:
			return
		q = [root]
		supportQ = []
		ans = []
		tmp = []
		level = 0
		while q:
			nod = q.pop(0)
			tmp.append(nod.data)
			if nod.left:
				supportQ.append(nod.left)
			if nod.right:
				supportQ.append(nod.right)
			if len(q) == 0:
				if level % 2 != 0:
					tmp = tmp[::-1]
				for i in tmp:
					ans.append(i)
				while supportQ:
					q.append(supportQ.pop(0))
				tmp = []
				level += 1
		return ans


class Solution:

	def zigZagTraversal(self, root):
		q = []
		ans = []
		flg = 1
		q.append(root)
		while len(q) != 0:
			tmp = []
			size = len(q)
			while size != 0:
				curr = q.pop(0)
				tmp.append(curr.data)
				if curr.left != None:
					q.append(curr.left)
				if curr.right != None:
					q.append(curr.right)
				size -= 1
			if flg % 2 == 0:
				tmp = tmp[::-1]
			for i in tmp:
				ans.append(i)
			flg += 1
		return ans


class Solution:

	def zigZagTraversal(self, root):
		q = []
		q.append(root)
		p = []
		f = 0
		while len(q) != 0:
			z = []
			n = len(q)
			for i in range(n):
				node = q.pop(0)
				z.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			if f % 2 != 0:
				z.reverse()
				for i in range(len(z)):
					p.append(z[i])
			else:
				for i in range(len(z)):
					p.append(z[i])
			f = f + 1
		return p


from collections import deque

class Solution:

	def zigZagTraversal(self, root):
		result = []
		queue = deque()
		queue.append(root)
		l = 0
		while len(queue) >= 1:
			lst = []
			size = len(queue)
			for i in range(size):
				curr = queue.popleft()
				lst.append(curr.data)
				if curr.left is not None:
					queue.append(curr.left)
				if curr.right is not None:
					queue.append(curr.right)
			if l % 2 == 0:
				for ele in lst:
					result.append(ele)
				lst = []
			else:
				for ele in lst[::-1]:
					result.append(ele)
				lst = []
			l = l + 1
		return result


class Solution:

	def zigZagTraversal(self, root):
		if root is None:
			return []
		res = []
		queue = []
		queue.append(root)
		reverse = True
		while queue:
			level = []
			for i in range(len(queue)):
				curr = queue.pop(0)
				level.append(curr.data)
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
			if not reverse:
				level.reverse()
			reverse = not reverse
			res += level
		return res


class Solution:

	def zigZagTraversal(self, root):
		if not root:
			return []
		queue = [[root]]
		ans = [root.data]
		flag = 0
		while queue:
			level = queue.pop(0)
			temp = []
			for node in level:
				if node.left:
					temp.append(node.left)
				if node.right:
					temp.append(node.right)
			if temp:
				queue.append(temp)
				if flag == 0:
					ans += list(reversed([node.data for node in temp]))
					flag = 1
				else:
					ans += [node.data for node in temp]
					flag = 0
		return ans


class Solution:

	def zigZagTraversal(self, root):
		q = [root]
		res = []
		left_to_right = True
		while len(q) != 0:
			size = len(q)
			ans = [0] * size
			for i in range(size):
				ind = i if left_to_right else size - i - 1
				node = q.pop(0)
				ans[ind] = node.data
				if node.left is not None:
					q.append(node.left)
				if node.right is not None:
					q.append(node.right)
			left_to_right = not left_to_right
			for i in ans:
				res.append(i)
		return res


from collections import deque, defaultdict

class Solution:

	def zigZagTraversal(self, root):
		if not root:
			return []
		li = defaultdict(list)
		q = deque([(root, 0)])
		while q:
			(node, con) = q.popleft()
			if node and con % 2 == 0:
				li[con].append(node.data)
			else:
				li[con].insert(0, node.data)
			if node.left:
				q.append((node.left, con + 1))
			if node.right:
				q.append((node.right, con + 1))
		li = list(li.values())
		ans = []
		for i in range(len(li)):
			for j in li[i]:
				ans.append(j)
		return ans


class Solution:

	def zigZagTraversal(self, root):
		q = [root]
		result = []
		level = 1
		while q:
			lst = []
			size = len(q)
			for i in range(size):
				ele = q.pop(0)
				lst.append(ele.data)
				if ele.left != None:
					q.append(ele.left)
				if ele.right != None:
					q.append(ele.right)
			if level % 2 == 0:
				result.extend(lst[::-1])
			else:
				result.extend(lst)
			level += 1
		return result


class Solution:

	def zigZagTraversal(self, root):
		if root is None:
			return
		(s1, s2, arr) = ([], [], [])
		s1.append(root)
		while len(s1) != 0 or len(s2) != 0:
			if len(s1) > 0:
				while len(s1) > 0:
					temp = s1.pop()
					arr.append(temp.data)
					if temp.left:
						s2.append(temp.left)
					if temp.right:
						s2.append(temp.right)
			if len(s2) > 0:
				while len(s2) > 0:
					temp = s2.pop()
					arr.append(temp.data)
					if temp.right:
						s1.append(temp.right)
					if temp.left:
						s1.append(temp.left)
		return arr


from collections import deque

class Solution:

	def zigZagTraversal(self, root):
		if root == None:
			return []
		flag = 0
		q = deque([root])
		ans = []
		while q:
			n = len(q)
			t = []
			for i in range(n):
				node = q.popleft()
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				t.append(node.data)
			if flag:
				ans.extend(t[::-1])
			else:
				ans.extend(t)
			flag ^= 1
		return ans


class Solution:

	def zigZagTraversal(self, root):
		result = []
		queue = [root]
		level = 0
		while len(queue) > 0:
			size = len(queue)
			lst = []
			for i in range(size):
				curr = queue.pop(0)
				lst.append(curr.data)
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
			if level % 2 != 0:
				result.extend(lst[::-1])
			else:
				result.extend(lst)
			level += 1
		return result


from collections import deque

class Solution:

	def zigZagTraversal(self, root):
		queue = deque()
		res = []
		left_to_right = True
		queue.append(root)
		while queue:
			size = len(queue)
			temp = [0] * size
			for i in range(size):
				node = queue.popleft()
				if left_to_right:
					index = i
				else:
					index = size - i - 1
				temp[index] = node.data
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			left_to_right = not left_to_right
			res.extend(temp)
		return res


from collections import deque, defaultdict

class Solution:

	def zigZagTraversal(self, root):
		result = []
		q = deque()
		q.append(root)
		left_to_right = True
		while q:
			size = len(q)
			ans = [-1] * size
			if left_to_right:
				for i in range(size):
					node = q.popleft()
					ans[i] = node.data
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
			else:
				for i in range(size - 1, -1, -1):
					node = q.popleft()
					ans[i] = node.data
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
			result.extend(ans)
			left_to_right = not left_to_right
		return result


from collections import deque, defaultdict

class Solution:

	def zigZagTraversal(self, root):
		dist_map = defaultdict(list)
		q = deque()
		q.append((root, 0))
		while q:
			(node, d) = q.popleft()
			dist_map[d].append(node.data)
			if node.left:
				q.append((node.left, d + 1))
			if node.right:
				q.append((node.right, d + 1))
		sorted_distances = sorted(dist_map.keys())
		ans = []
		left_to_right = True
		for d in sorted_distances:
			if left_to_right:
				ans.extend(dist_map[d])
			else:
				ans.extend(dist_map[d][::-1])
			left_to_right = not left_to_right
		return ans


class Solution:

	def zigZagTraversal(self, root):
		res = []
		s1 = []
		s2 = []
		s1.append(root)
		while len(s1) != 0 or len(s2) != 0:
			while len(s1) != 0:
				node = s1.pop()
				if node:
					res.append(node.data)
					if node.left:
						s2.append(node.left)
					if node.right:
						s2.append(node.right)
			while len(s2) != 0:
				node = s2.pop()
				if node:
					res.append(node.data)
					if node.right:
						s1.append(node.right)
					if node.left:
						s1.append(node.left)
		return res


class Solution:

	def zigZagTraversal(self, root):
		if root is None:
			return []
		result = []
		final = []
		queue = deque([root])
		level = 0
		while queue:
			level_size = len(queue)
			level_nodes = []
			for _ in range(level_size):
				node = queue.popleft()
				level_nodes.append(node.data)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			if level % 2 == 1:
				level_nodes.reverse()
			result.append(level_nodes)
			level += 1
		for i in result:
			for a in i:
				final.append(a)
		return final


class Solution:

	def zigZagTraversal(self, root):
		if root is None:
			return []
		level = 0
		res = []
		q = deque()
		q.append(root)
		while q:
			count = len(q)
			level += 1
			l = []
			for i in range(count):
				currN = q.popleft()
				l.append(currN.data)
				if currN.left:
					q.append(currN.left)
				if currN.right:
					q.append(currN.right)
			if level % 2 != 0:
				res = res + l
			else:
				res = res + l[::-1]
		return res


class Solution:

	def zigZagTraversal(self, root):
		if root is None:
			return []
		flag = 0
		res = []
		q = deque()
		q.append(root)
		while q:
			count = len(q)
			for i in range(count):
				currN = q.popleft() if flag == 0 else q.pop()
				res.append(currN.data)
				if flag == 0:
					if currN.left:
						q.append(currN.left) if flag == 0 else q.appendleft(currN.left)
					if currN.right:
						q.append(currN.right) if flag == 0 else q.appendleft(currN.right)
				else:
					if currN.right:
						q.append(currN.right) if flag == 0 else q.appendleft(currN.right)
					if currN.left:
						q.append(currN.left) if flag == 0 else q.appendleft(currN.left)
			flag = 1 if flag == 0 else 0
		return res


from collections import deque

class Solution:

	def zigZagTraversal(self, root):
		res = []
		queue = deque()
		queue.append(root)
		queue.append(None)
		flag = True
		inter = []
		while len(queue) != 0:
			temp = queue.popleft()
			if not temp:
				res = res + (inter if flag else inter[::-1])
				inter = []
				flag = not flag
				if len(queue) != 0:
					queue.append(None)
			else:
				inter.append(temp.data)
				if temp.left:
					queue.append(temp.left)
				if temp.right:
					queue.append(temp.right)
		return res


class Solution:

	def zigZagTraversal(self, root):
		res = []
		if root is None:
			return ans
		q = []
		q.append(root)
		leftToRight = True
		while len(q) > 0:
			size = len(q)
			ans = [None] * size
			for i in range(size):
				Node = q[0]
				val = Node.data
				q.pop(0)
				index = i if leftToRight else size - i - 1
				ans[index] = val
				if Node.left:
					q.append(Node.left)
				if Node.right:
					q.append(Node.right)
			leftToRight = not leftToRight
			for i in ans:
				res.append(i)
		return res


from collections import deque

class Solution:

	def zigZagTraversal(self, root):
		q = deque([])
		stack = []
		q.append(root)
		stack.append(root.data)
		l = 1
		while len(q) > 0:
			n = len(q)
			for i in range(n):
				if l % 2 == 0:
					temp = q[-1]
					q.pop()
				else:
					temp = q[0]
					q.popleft()
				if l % 2 != 0:
					if temp.right:
						q.append(temp.right)
						stack.append(temp.right.data)
					if temp.left:
						q.append(temp.left)
						stack.append(temp.left.data)
				elif l % 2 == 0:
					if temp.left:
						q.appendleft(temp.left)
						stack.append(temp.left.data)
					if temp.right:
						q.appendleft(temp.right)
						stack.append(temp.right.data)
			l += 1
		return stack


class Solution:

	def zigZagTraversal(self, root):
		if root is None:
			return
		ans = []
		queue = [root]
		flag = False
		while len(queue) != 0:
			n = len(queue)
			level = []
			for i in range(n):
				node = queue[0]
				queue.pop(0)
				level.append(node.data)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			flag = not flag
			if flag == False:
				level = level[::-1]
			for i in range(n):
				ans.append(level[i])
		return ans