Given a Binary Tree. Find the difference between the sum of node values at even levels and the sum of node values at the odd levels.
Example 1:
Input:
            1
          /   \
         2     3
Output: -4
Explanation:
sum at odd levels - sum at even levels
= (1)-(2+3) = 1-5 = -4
Example 2:
Input:
            10
          /    \
        20      30
       /  \         
     40    60      
Output: 60
Explanation:
sum at odd levels - sum at even levels
= (10+40+60) - (20+30)
= 110 - 50
= 60
Your Task:  
You dont need to read input or print anything. Complete the function getLevelDiff() which takes root node as input parameter and returns an integer.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of tree)
 
Constraints:
1 ≤ N ≤ 10^5

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
'''
class Solution:
    def getLevelDiff(self, root):
        # Code here


Solutions:
class Solution:

	def getLevelDiff(self, root):
		if root == None:
			return 0
		q = []
		q.append(root)
		reverse = True
		s = 0
		while q != []:
			c = len(q)
			for i in range(c):
				val = q.pop(0)
				if reverse == True:
					s += val.data
				else:
					s -= val.data
				if val.left != None:
					q.append(val.left)
				if val.right != None:
					q.append(val.right)
			reverse = ~reverse
		return s


class Solution:

	def getLevelDiff(self, root):
		if root is None:
			return 0
		return root.data - self.getLevelDiff(root.left) - self.getLevelDiff(root.right)


from collections import deque

class Solution:

	def getLevelDiff(self, root):
		queue = deque()
		queue.append(root)
		odd_sum = 0
		even_sum = 0
		level = 0
		while queue:
			size = len(queue)
			for _ in range(size):
				curr = queue.popleft()
				if level % 2 == 0:
					even_sum += curr.data
				else:
					odd_sum += curr.data
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
			level = level + 1
		return even_sum - odd_sum


class Solution:

	def getLevelDiff(self, root):
		o = []
		e = []
		s = [root]
		res = []
		level = 0
		while s:
			new = []
			if s:
				if level % 2 != 0:
					e.append(s)
				else:
					o.append(s)
			for i in s:
				node = i
				if node.left:
					new.append(node.left)
				if node.right:
					new.append(node.right)
			if new:
				s = new
			else:
				break
			level += 1
		o1 = []
		e1 = []
		for i in o:
			o1 += i
		for i in e:
			e1 += i
		for i in range(len(o1)):
			o1[i] = o1[i].data
		for i in range(len(e1)):
			e1[i] = e1[i].data
		return sum(o1) - sum(e1)


class Solution:

	def getLevelDiff(self, root):
		if root is None:
			return
		q = []
		c = 1
		q.append(root)
		odd = []
		even = []
		while len(q) > 0:
			t = []
			n = len(q)
			for i in range(n):
				temp = q.pop(0)
				t.append(temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			if c % 2 == 0:
				for i in t:
					even.append(i)
			else:
				for z in t:
					odd.append(z)
			c += 1
		return sum(odd) - sum(even)


class Solution:

	def getLevelDiff(self, root):
		if not root:
			return -1
		l = 1
		q = []
		q.append(root)
		o = []
		e = []
		while q:
			t = []
			for i in range(len(q)):
				n = q.pop(0)
				t.append(n.data)
				if n.left:
					q.append(n.left)
				if n.right:
					q.append(n.right)
			if l % 2 == 0:
				for i in t:
					e.append(i)
			else:
				for i in t:
					o.append(i)
			l += 1
		return sum(o) - sum(e)


class Solution:

	def getLevelDiff(self, root):
		flag = True
		q = [root]
		oddS = 0
		evenS = 0
		while q:
			n = len(q)
			temp = 0
			for i in range(n):
				node = q.pop(0)
				temp += node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			if flag:
				oddS += temp
			else:
				evenS += temp
			flag = not flag
		return oddS - evenS


from collections import deque

class Solution:

	def getLevelDiff(self, root):
		(es, os) = (0, 0)
		level = 1
		q = deque([root, None])
		while len(q) != 1:
			ele = q.popleft()
			if ele:
				if level % 2 == 0:
					es += ele.data
				else:
					os += ele.data
				if ele.left:
					q.append(ele.left)
				if ele.right:
					q.append(ele.right)
			else:
				level += 1
				q.append(None)
		return os - es


class Solution:

	def getLevelDiff(self, root):
		if root is None:
			return None
		q = []
		q.append(root)
		j = 1
		(os, es) = (0, 0)
		while q:
			s = 0
			l = len(q)
			for i in range(1, l + 1):
				n = q.pop(0)
				s += n.data
				if n.left:
					q.append(n.left)
				if n.right:
					q.append(n.right)
			if j % 2:
				os += s
			else:
				es += s
			j += 1
		return os - es


class Solution:

	def getLevelDiff(self, root):
		flag = 0
		ans = 0
		q = [root]
		while q:
			num = 0
			for _ in range(len(q)):
				node = q.pop(0)
				num += node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			if flag == 0:
				ans += num
				flag = 1
			else:
				flag = 0
				ans -= num
		return ans


class Solution:

	def getLevelDiff(self, root):
		even = 0
		odd = 0
		lvl = 0
		if root == None:
			return
		li = []
		li.append(root)
		while len(li):
			size = len(li)
			lvl += 1
			while size:
				temp = li[0]
				li.pop(0)
				if lvl % 2 == 0:
					even += temp.data
				else:
					odd += temp.data
				if temp.left:
					li.append(temp.left)
				if temp.right:
					li.append(temp.right)
				size -= 1
		return odd - even


from collections import deque

class Solution:

	def getLevelDiff(self, root):
		dQ = deque()
		level1 = level2 = 0
		if root != None:
			dQ.append(root)
		track = 0
		while dQ:
			times = len(dQ)
			track += 1
			for i in range(times):
				havenode = dQ.popleft()
				(level1, level2) = [level1 + havenode.data, level2] if track % 2 == 1 else [level1, level2 + havenode.data]
				if havenode.left != None:
					dQ.append(havenode.left)
				if havenode.right != None:
					dQ.append(havenode.right)
		return level1 - level2


class Solution:

	def getLevelDiff(self, root):
		global esum
		global osum
		esum = 0
		osum = 0

		def helper(root, c):
			global esum
			global osum
			if root == None:
				return
			if c % 2 == 0:
				osum += root.data
			else:
				esum += root.data
			helper(root.left, c + 1)
			helper(root.right, c + 1)
		helper(root, 0)
		return osum - esum


class Solution:

	def fun(self, root, level, l):
		if root == None:
			return
		if level >= len(l):
			l.append([])
		l[level].append(root.data)
		self.fun(root.left, level + 1, l)
		self.fun(root.right, level + 1, l)

	def getLevelDiff(self, root):
		l = []
		self.fun(root, 0, l)
		(s1, s2) = (0, 0)
		for i in range(len(l)):
			if i % 2 == 0:
				s1 += sum(l[i])
			else:
				s2 += sum(l[i])
		return s1 - s2


from collections import deque

class Solution:

	def getLevelDiff(self, root):
		if root is None:
			return 0
		return root.data - self.getLevelDiff(root.left) - self.getLevelDiff(root.right)
		return result


from collections import deque

class Solution:

	def getLevelDiff(self, root):
		q = deque()
		q.appendleft(root)
		result = 0
		sum = True
		while q:
			temp_sum = 0
			size = len(q)
			for i in range(size):
				node = q.pop()
				temp_sum += node.data
				if node.left:
					q.appendleft(node.left)
				if node.right:
					q.appendleft(node.right)
			if sum:
				result += temp_sum
			else:
				result -= temp_sum
			sum = not sum
		return result


import queue

class Solution:

	def getLevelDiff(self, root):
		q = []
		q.append(root)
		result = 0
		sum = True
		while q:
			temp_sum = 0
			size = len(q)
			for i in range(size):
				node = q.pop(0)
				temp_sum += node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			if sum:
				result += temp_sum
			else:
				result -= temp_sum
			sum = not sum
		return result


from collections import deque as d

class Solution:

	def getLevelDiff(self, root):
		l = d()
		l.appendleft(root)
		l.appendleft(' ')
		ll = []
		c = 1
		os = 0
		es = 0
		while l:
			a = l.pop()
			if a == ' ':
				if c % 2 != 0:
					os += sum(ll)
				else:
					es += sum(ll)
				ll = []
				if l:
					l.appendleft(' ')
				c += 1
			else:
				ll.append(a.data)
				if a.left:
					l.appendleft(a.left)
				if a.right:
					l.appendleft(a.right)
		return os - es


class Solution:

	def solve(self, root, odd, even, l):
		if root == None:
			return
		if l % 2 == 0:
			even.append(root.data)
		else:
			odd.append(root.data)
		l += 1
		self.solve(root.left, odd, even, l)
		self.solve(root.right, odd, even, l)
		l -= 1

	def getLevelDiff(self, root):
		odd = []
		even = []
		l = 0
		self.solve(root, odd, even, l)
		k = sum(even) - sum(odd)
		return k


from collections import deque

class Solution:

	def getLevelDiff(self, root):
		q = deque()
		q.append(root)
		s = root.data
		lvl = 1
		while q:
			k = len(q)
			lvl += 1
			for i in range(k):
				popped = q.popleft()
				if popped.left:
					q.append(popped.left)
					if lvl % 2 == 0:
						s -= popped.left.data
					else:
						s += popped.left.data
				if popped.right:
					q.append(popped.right)
					if lvl % 2 == 0:
						s -= popped.right.data
					else:
						s += popped.right.data
		return s


class Solution:

	def getLevelDiff(self, root):
		even = 0
		odd = 0

		def lev(rt, level):
			nonlocal even, odd
			if not rt:
				return
			if level % 2 == 0:
				even += rt.data
			if level % 2 == 1:
				odd += rt.data
			lev(rt.left, level + 1)
			lev(rt.right, level + 1)
		lev(root, 1)
		return odd - even


class Solution:

	def getLevelDiff(self, root):
		odd = 0
		even = 0
		from collections import deque
		q = deque()
		q.append(root)
		c = 1
		while q:
			size = len(q)
			x = 0
			for i in range(size):
				node = q.popleft()
				x += node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			if c & 1:
				odd += x
			else:
				even += x
			c += 1
		return odd - even


class Solution:

	def getLevelDiff(self, root):
		l = []
		q = []
		k = [0]
		m = -1
		q.append(root)
		while q:
			z = q.pop(0)
			x = k.pop(0)
			if m != x:
				m = x
				l.append([])
			l[-1].append(z.data)
			if z.left is not None:
				q.append(z.left)
				k.append(x + 1)
			if z.right is not None:
				q.append(z.right)
				k.append(x + 1)
		odd = 0
		for x in range(0, len(l), 2):
			odd += sum(l[x])
		even = 0
		for x in range(1, len(l), 2):
			even += sum(l[x])
		return odd - even


class Solution:

	def getLevelDiff(self, root):
		dd = {}
		stck = []
		stck.append(root)
		level = 1
		cnt = 1
		while stck:
			total = 0
			for i in range(cnt):
				popped = stck.pop(0)
				total += popped.data
				if popped.left:
					stck.append(popped.left)
				if popped.right:
					stck.append(popped.right)
			cnt = len(stck)
			dd[level] = total
			level += 1
		diff = 0
		for i in dd.keys():
			if i % 2 == 0:
				diff -= dd[i]
			else:
				diff += dd[i]
		return diff


class Solution:

	def getLevelDiff(self, root):
		self.ans = 0

		def cal(root, d):
			if root == None:
				return
			if d % 2 == 0:
				self.ans -= root.data
			else:
				self.ans += root.data
			cal(root.left, d + 1)
			cal(root.right, d + 1)
		cal(root, 1)
		return self.ans


class Solution:

	def getLevelDiff(self, root):
		q = [root]
		even = 0
		odd = 0
		count = 1
		while q:
			list = []
			for i in q:
				list.append(i.data)
			if count % 2 != 0:
				odd += sum(list)
			else:
				even += sum(list)
			for _ in range(len(q)):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			count += 1
		return odd - even


from collections import deque

class Solution:

	def getLevelDiff(self, root):
		q = deque([root])
		k = []
		while q:
			n = len(q)
			l = []
			for _ in range(n):
				node = q.popleft()
				l.append(node.data)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			k.append(sum(l))
		o = e = 0
		for i in range(len(k)):
			if i % 2 == 0:
				e += k[i]
			else:
				o += k[i]
		return e - o


class Solution:

	def getLevelDiff(self, root):
		return dfs(root, 0)

def dfs(n, l):
	if not n:
		return 0
	if not n.left and (not n.right):
		return n.data if l % 2 == 0 else -n.data
	children = dfs(n.left, l + 1) + dfs(n.right, l + 1)
	me = n.data if l % 2 == 0 else -n.data
	return children + me


class Solution:

	def getLevelDiff(self, root):
		global sm
		sm = 0

		def diff(root, h):
			global sm
			if root is None:
				return
			if h % 2 == 0:
				sm = sm + root.data
			else:
				sm = sm - root.data
			diff(root.left, h + 1)
			diff(root.right, h + 1)
		diff(root, 0)
		return sm


class Solution:

	def getLevelDiff(self, root):
		c = 1
		if not root:
			return []
		s = 0
		q = []
		q.append(root)
		while q:
			a = []
			le = len(q)
			for i in range(le):
				k = q.pop(0)
				a.append(k.data)
				if k.left:
					q.append(k.left)
				if k.right:
					q.append(k.right)
			if c & 1:
				s += sum(a)
			else:
				s -= sum(a)
			c += 1
		return s


class Solution:

	def getLevelDiff(self, root):
		sum_even = 0
		sum_odd = 0
		st = []
		counter = 0
		if root is None:
			return 0
		st.append(root)
		while len(st) > 0:
			counter += 1
			t = []
			while len(st) != 0:
				x = st.pop()
				if x.left is not None:
					t.append(x.left)
				if x.right is not None:
					t.append(x.right)
				if counter % 2 == 0:
					sum_even += x.data
				else:
					sum_odd += x.data
			st = t
		return sum_odd - sum_even


def levelOrder(root):
	bfs = []
	if root is None:
		return bfs
	q = deque([])
	q.append(root)
	while q:
		lvl_size = len(q)
		curr_lvl = []
		for i in range(lvl_size):
			curr = q.popleft()
			curr_lvl.append(curr.data)
			if curr.left is not None:
				q.append(curr.left)
			if curr.right is not None:
				q.append(curr.right)
		bfs.append(curr_lvl)
	return bfs

class Solution:

	def getLevelDiff(self, root):
		sumi = 0
		count = 0
		a = levelOrder(root)
		while a:
			s = a.pop(0)
			if count % 2 == 0:
				sumi += sum(s)
			else:
				sumi -= sum(s)
			count += 1
		return sumi


class Solution:

	def getLevelDiff(self, root):
		c = 1
		s1 = 0
		s2 = 0
		queue = [root]
		while queue != []:
			t = []
			for i in range(len(queue)):
				curr = queue[0]
				t.append(curr.data)
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
				queue.pop(0)
			if c % 2 == 1:
				s1 += sum(t)
				c += 1
			elif c % 2 != 1:
				s2 += sum(t)
				c += 1
		return s1 - s2


class Solution:

	def getLevelDiff(self, root):
		es = [0]
		os = [0]
		level = [0]
		self.Util(root, es, os, level, 1)
		return os[0] - es[0]

	def Util(self, root, es, os, level, l):
		if not root:
			return
		if l % 2 == 0:
			es[0] += root.data
		else:
			os[0] += root.data
		self.Util(root.left, es, os, level, l + 1)
		self.Util(root.right, es, os, level, l + 1)


class Solution:

	def getLevelDiff(self, root):
		odd = []
		even = []
		q = []
		q.append(root)
		x = 1
		while q:
			l = len(q)
			lis = []
			for i in range(l):
				temp = q.pop(0)
				lis.append(temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			if x % 2 == 0:
				even.extend(lis)
			else:
				odd.extend(lis)
			x += 1
		return sum(odd) - sum(even)


class Solution:

	def getLevelDiff(self, root):
		q = []
		od = 0
		ev = 0
		q.append(root)
		l = 0
		while q:
			l += 1
			n = len(q)
			ans = 0
			while n > 0:
				k = q.pop(0)
				ans += k.data
				if k.left:
					q.append(k.left)
				if k.right:
					q.append(k.right)
				n -= 1
			if l % 2 == 0:
				ev += ans
			else:
				od += ans
		return od - ev


class Solution:

	def getLevelDiff(self, root, level=1):
		if root.left == None and root.right == None:
			if level % 2 == 1:
				return root.data
			else:
				return -root.data
		lowlevelleft = 0
		lowlevelright = 0
		if root.left != None:
			lowlevelleft = self.getLevelDiff(root.left, level + 1)
		if root.right != None:
			lowlevelright = self.getLevelDiff(root.right, level + 1)
		if level % 2 == 0:
			return lowlevelleft + lowlevelright - root.data
		else:
			return lowlevelleft + lowlevelright + root.data


import collections

class Solution:

	def getLevelDiff(self, root):
		q = collections.deque()
		q.append(root)
		odd = True
		odd_tot = 0
		even_tot = 0
		while q:
			qLen = len(q)
			tot = 0
			for i in range(qLen):
				cur = q.popleft()
				if cur.left:
					q.append(cur.left)
				if cur.right:
					q.append(cur.right)
				tot += cur.data
			if odd:
				odd_tot += tot
				odd = False
			else:
				even_tot += tot
				odd = True
		return odd_tot - even_tot


class Solution:

	def getLevelDiff(self, root):
		d = []
		g = {}
		m = []
		d.append(1)
		m.append(root)
		while len(m) != 0:
			c = m.pop(0)
			x = d.pop(0)
			if x not in g:
				g[x] = [c.data]
			else:
				g[x].append(c.data)
			if c.left != None:
				m.append(c.left)
				d.append(x + 1)
			if c.right != None:
				m.append(c.right)
				d.append(x + 1)
		odd = 0
		even = 0
		for h in g:
			if h % 2 == 0:
				for j in range(0, len(g[h])):
					even = even + g[h][j]
			else:
				for j in range(0, len(g[h])):
					odd = odd + g[h][j]
		return odd - even


class Solution:

	def getLevelDiff(self, root):
		sum = [0, 0]
		self.findSum(root, 1, sum)
		return sum[0] - sum[1]

	def findSum(self, root, level, sum):
		if not root:
			return None
		if level % 2 == 0:
			sum[1] += root.data
		else:
			sum[0] += root.data
		self.findSum(root.left, level + 1, sum)
		self.findSum(root.right, level + 1, sum)


class Solution:

	def getLevelDiff(self, root):
		if root == None:
			return
		q = [root]
		c = 1
		(s1, s2) = (0, 0)
		while q:
			l = []
			s = len(q)
			for i in range(len(q)):
				t = q.pop(0)
				l.append(t.data)
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
			if c == 1:
				s1 = s1 + sum(l)
				c = 0
			else:
				s2 = s2 + sum(l)
				c = 1
		return s1 - s2


class Solution:

	def getLevelDiff(self, root):
		C = self.reverseLevelOrder(root)
		x = 0
		for i in range(len(C)):
			if i % 2 == 0:
				x += sum(C[i])
			else:
				x -= sum(C[i])
		return x

	def reverseLevelOrder(self, root):
		A = []
		B = []
		C = []
		D = []
		if root is None:
			return A
		A.append(root)
		while len(A) > 0:
			while len(A) > 0:
				node = A.pop(0)
				B.append(node.data)
				if node.left is not None:
					D.append(node.left)
				if node.right is not None:
					D.append(node.right)
			A.extend(D)
			D = []
			C.append(B)
			B = []
		return C


class Solution:

	def getLevelDiff(self, root):
		ans = [0] * 1

		def fun(root, level):
			if root == None:
				return
			if level % 2 == 0:
				ans[0] += root.data
			else:
				ans[0] -= root.data
			fun(root.left, level + 1)
			fun(root.right, level + 1)
		fun(root, 0)
		return ans[0]


class Solution:

	def getLevelDiff(self, root):
		l = 0
		q = [root]
		(res, ans) = ([], [])
		if root == None:
			return None
		while q:
			for i in range(len(q)):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				if l % 2 == 0:
					res.append(node.data)
				else:
					ans.append(node.data)
			l += 1
		return sum(res) - sum(ans)


from collections import deque

class Solution:

	def getLevelDiff(self, root):

		def traversal(root, level):
			nonlocal sum1, sum2
			if root == None:
				return None
			if level % 2 == 0:
				sum1 += root.data
			else:
				sum2 += root.data
			if root.left:
				traversal(root.left, level + 1)
			if root.right:
				traversal(root.right, level + 1)
		(sum1, sum2) = (0, 0)
		traversal(root, 0)
		return sum1 - sum2


class Solution:

	def getLevelDiff(self, root):
		q = []
		q.append(root)
		q.append('$')
		odd = 0
		even = 0
		level = 1
		while len(q) > 0:
			t = q.pop(0)
			if t == '$':
				if len(q) > 0:
					q.append('$')
					level += 1
			else:
				if t.left is not None:
					q.append(t.left)
				if t.right is not None:
					q.append(t.right)
				if level % 2 != 0:
					odd += t.data
				else:
					even += t.data
		return odd - even


class Solution:

	def getLevelDiff(self, root):
		mylist = [0, 0]
		if not root:
			return 0

		def help(root, lvl):
			if lvl % 2 == 0:
				mylist[0] += root.data
			else:
				mylist[1] += root.data
			if root.left:
				help(root.left, lvl + 1)
			if root.right:
				help(root.right, lvl + 1)
			return mylist[0] - mylist[1]
		return help(root, 0)


class Solution:

	def getLevelDiff(self, root):
		return self.myFunc(root, 0)

	def myFunc(self, root, level):
		if not root:
			return 0
		level += 1
		summa = root.data
		if level % 2 == 0:
			summa *= -1
		summa += self.myFunc(root.left, level)
		summa += self.myFunc(root.right, level)
		return summa


class Solution:

	def getLevelDiff(self, root):
		if root == None:
			return 0
		leftsum = self.getLevelDiff(root.left)
		rightsum = self.getLevelDiff(root.right)
		return root.data - leftsum - rightsum


class Solution:

	def in_order(self, root, lvl, nv):
		if root is None:
			return
		self.in_order(root.left, lvl + 1, nv)
		self.in_order(root.right, lvl + 1, nv)
		if lvl not in nv:
			nv[lvl] = [root.data]
		else:
			nv[lvl].append(root.data)

	def getLevelDiff(self, root):
		nv = {}
		self.in_order(root, 0, nv)
		osum = 0
		esum = 0
		for (k, v) in nv.items():
			if k % 2:
				esum += sum(v)
			else:
				osum += sum(v)
		return osum - esum


class Solution:

	def getLevelDiff(self, root):
		ans = [0, 0]
		if not root:
			return 0
		curr = [root]
		i = 0
		while curr:
			next_level = []
			while curr:
				v = curr.pop(0)
				ans[i % 2] += v.data
				if v.left:
					next_level.append(v.left)
				if v.right:
					next_level.append(v.right)
			i += 1
			curr = next_level
		return ans[0] - ans[1]


class Solution:

	def getNode(self, arr, root, d):
		if not root:
			return
		arr.append([root.data, d])
		self.getNode(arr, root.right, d + 1)
		self.getNode(arr, root.left, d + 1)

	def getLevelDiff(self, root):
		arr = []
		self.getNode(arr, root, 0)
		sum1 = 0
		sum2 = 0
		dep = len(arr)
		for i in range(0, dep):
			d = arr[i][1] + 1
			if d % 2 == 0:
				sum2 = sum2 + arr[i][0]
			else:
				sum1 = sum1 + arr[i][0]
		return sum1 - sum2


class Solution:

	def getLevelDiff(self, root):
		if root is None:
			return None
		q = [root]
		ans = root.data
		flag = True
		while len(q) > 0:
			n = len(q)
			temp = 0
			for i in range(0, n):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
					temp += node.left.data
				if node.right:
					q.append(node.right)
					temp += node.right.data
			if flag:
				ans -= temp
				flag = False
			else:
				ans += temp
				flag = True
		return ans


class Solution:

	def getLevelDiff(self, root):

		def helper(root):
			nonlocal odd_sum, even_sum
			nonlocal level
			if root is None:
				return
			level += 1
			if level % 2 == 0:
				even_sum += root.data
			else:
				odd_sum += root.data
			helper(root.left)
			helper(root.right)
			level -= 1
			return
		(odd_sum, even_sum) = (0, 0)
		level = 0
		helper(root)
		return odd_sum - even_sum


class Solution:

	def __init__(self):
		self.even = 0
		self.odd = 0

	def pre(self, root, l):
		if root == None:
			return
		if l % 2 == 1:
			self.odd += root.data
		else:
			self.even += root.data
		if root.left != None:
			self.pre(root.left, l + 1)
		if root.right != None:
			self.pre(root.right, l + 1)

	def getLevelDiff(self, root):
		self.pre(root, 1)
		return self.odd - self.even


class Solution:

	def getLevelDiff(self, root):
		q = deque()
		q.append(root)
		q.append(None)
		l = []
		m = []
		while len(q) > 1:
			cur = q.popleft()
			if cur == None:
				l.append(m)
				m = []
				q.append(None)
				continue
			m.append(cur.data)
			if cur.left != None:
				q.append(cur.left)
			if cur.right != None:
				q.append(cur.right)
		if m:
			l.append(m)
		os = 0
		es = 0
		for i in range(len(l)):
			if i % 2 == 0:
				os += sum(l[i])
			else:
				es += sum(l[i])
		t = os - es
		return t


class Solution:

	def getLevelDiff(self, root):
		q = [root]
		level = 1
		sume = 0
		sumo = 0
		while q:
			l = len(q)
			for i in range(l):
				if len(q) != 0:
					x = q.pop(0)
					if level % 2 == 0:
						sume += x.data
					else:
						sumo += x.data
					if i == l - 1:
						level += 1
					if x.left:
						q.append(x.left)
					if x.right:
						q.append(x.right)
		return sumo - sume


class Solution:

	def getLevelDiff(self, root):
		d = {}
		l1 = []
		l2 = []
		level = 1
		helper(root, level, d)
		for i in d:
			if i % 2 == 0:
				l1.append(sum(d[i]))
			else:
				l2.append(sum(d[i]))
		return sum(l2) - sum(l1)

def helper(root, level, d):
	if root:
		if root == 'N':
			return
		else:
			if level not in d:
				d[level] = [root.data]
			else:
				d[level].append(root.data)
			helper(root.left, level + 1, d)
			helper(root.right, level + 1, d)


class Solution:

	def getLevelDiff(self, root):
		q = []
		q.append(root)
		sum_o = 0
		sum_e = 0
		a = 0
		while q:
			n = len(q)
			for i in range(n):
				curr = q.pop(0)
				if a % 2 == 0:
					sum_o = sum_o + curr.data
				else:
					sum_e = sum_e + curr.data
				if curr.left != None:
					q.append(curr.left)
				if curr.right != None:
					q.append(curr.right)
			a += 1
		return sum_o - sum_e


class Solution:

	def __init__(self):
		self.odd = 0
		self.even = 0

	def getleveldiffutil(self, root, flag):
		if root is None:
			return None
		if flag == True:
			self.odd += root.data
		else:
			self.even += root.data
		self.getleveldiffutil(root.left, not flag)
		self.getleveldiffutil(root.right, not flag)

	def getLevelDiff(self, root):
		flag = True
		self.getleveldiffutil(root, flag)
		return self.odd - self.even


class Solution:

	def getLevelDiff(self, root):
		q = []
		q.append(root)
		level = 1
		odd_sum = 0
		even_sum = 0
		while q:
			for _ in range(len(q)):
				curr = q.pop(0)
				data = curr.data
				if level & 1:
					odd_sum += data
				else:
					even_sum += data
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
			level += 1
		return odd_sum - even_sum


from collections import deque

class Solution:

	def getLevelDiff(self, root):
		if not root:
			return 0
		q = deque([root])
		(res, level) = (0, 1)
		while q:
			for _ in range(len(q)):
				node = q.popleft()
				if level & 1:
					res += node.data
				else:
					res -= node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			level += 1
		return res


def evenOddLevelDifference(root):
	if not root:
		return 0
	q = []
	q.append(root)
	level = 0
	evenSum = 0
	oddSum = 0
	while len(q):
		size = len(q)
		level += 1
		while size > 0:
			temp = q[0]
			q.pop(0)
			if level % 2 == 0:
				evenSum += temp.data
			else:
				oddSum += temp.data
			if temp.left:
				q.append(temp.left)
			if temp.right:
				q.append(temp.right)
			size -= 1
	return oddSum - evenSum

class Solution:

	def getLevelDiff(self, root):
		return evenOddLevelDifference(root)


class Solution:

	def getLevelDiff(self, root):
		(a, b) = (0, 0)

		def lev(root, l):
			nonlocal a, b
			if not root:
				return
			if l % 2 != 0:
				a += root.data
			else:
				b += root.data
			lev(root.left, l + 1)
			lev(root.right, l + 1)
			return a - b
		return lev(root, 1)


class Solution:

	def getLevelDiff(self, root):
		even = 0
		odd = 0
		evenb = True
		queue = [root]
		elements = 1
		newelements = 0
		while len(queue) > 0:
			root = queue.pop(0)
			if evenb:
				even += root.data
			else:
				odd += root.data
			elements -= 1
			if root.left != None:
				queue.append(root.left)
				newelements += 1
			if root.right != None:
				queue.append(root.right)
				newelements += 1
			if elements == 0:
				elements += newelements
				newelements = 0
				evenb = not evenb
		return even - odd


class Solution:

	def getLevelDiff(self, root):
		odd = 0
		even = 0

		def dfs(root, level):
			nonlocal even
			nonlocal odd
			if not root:
				return
			dfs(root.left, level + 1)
			dfs(root.right, level + 1)
			if level % 2 == 0:
				even += root.data
			else:
				odd += root.data
			return odd - even
		return dfs(root, 1)


class Solution:

	def getLevelDiff(self, root):
		level = 0
		evenStack = []
		oddStack = []

		def oddEvenLevels(root, level):
			if root == None:
				return
			if level % 2 == 0:
				evenStack.append(root.data)
			else:
				oddStack.append(root.data)
			oddEvenLevels(root.left, level + 1)
			oddEvenLevels(root.right, level + 1)
		oddEvenLevels(root, 0)
		evenValue = 0
		for i in evenStack:
			evenValue = evenValue + i
		oddValue = 0
		for i in oddStack:
			oddValue = oddValue + i
		return evenValue - oddValue


class Solution:

	def getLevelDiff(self, root):
		if root is None:
			return 0
		if root.left is None and root.right is None:
			return root.data
		freq = {}
		self.traversal(root, freq, 1)
		return freq['o'] - freq['e']

	def traversal(self, root, freq, level):
		if root is None:
			return
		if level % 2 == 0:
			if 'e' in freq.keys():
				freq['e'] += root.data
			else:
				freq['e'] = root.data
		elif 'o' in freq.keys():
			freq['o'] += root.data
		else:
			freq['o'] = root.data
		self.traversal(root.left, freq, level + 1)
		self.traversal(root.right, freq, level + 1)


class Solution:

	def getLevelDiff(self, root):
		oddArr = []
		evenArr = []
		self.getLevelDiffAux(root, 1, oddArr, evenArr)
		return sum(oddArr) - sum(evenArr)

	def getLevelDiffAux(self, node, level, oddArr, evenArr):
		if node is None:
			return
		elif level % 2 == 0:
			evenArr.append(node.data)
		else:
			oddArr.append(node.data)
		self.getLevelDiffAux(node.left, level + 1, oddArr, evenArr)
		self.getLevelDiffAux(node.right, level + 1, oddArr, evenArr)


class Solution:

	def getLevelDiff(self, root):

		def helper(root, mp, k):
			if root:
				if k in mp:
					mp[k] += root.data
				else:
					mp[k] = root.data
				helper(root.left, mp, k + 1)
				helper(root.right, mp, k + 1)
			return mp
		mp = helper(root, {}, 0)
		e = 0
		o = 0
		for i in mp:
			if i & 1 == 0:
				e += mp[i]
			else:
				o += mp[i]
		return e - o


class Solution:

	def getLevelDiff(self, root):

		def helper(x):
			ans = []
			q = []
			t = 0
			if not x:
				return None
			q.append(x)
			while q:
				l = len(q)
				for i in range(l):
					a = q.pop(0)
					if a.left:
						q.append(a.left)
					if a.right:
						q.append(a.right)
					t += a.data
				ans.append(t)
				t = 0
			return ans
		a = helper(root)
		b = 0
		c = 0
		for i in range(len(a)):
			if i % 2 == 0:
				b += a[i]
			else:
				c += a[i]
		return b - c


from collections import deque

class Solution:

	def getLevelDiff(self, root):
		q = deque()
		q.append(root)
		evenLvl = 0
		oddLvl = 0
		flag = True
		while q:
			for i in range(len(q)):
				temp = q.popleft()
				if flag:
					oddLvl += temp.data
				else:
					evenLvl += temp.data
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
			if flag:
				flag = False
			else:
				flag = True
		return oddLvl - evenLvl


import collections
from collections import deque

class Solution:

	def getLevelDiff(self, root):
		res = []
		sum1 = 0
		sum2 = 0
		q = collections.deque()
		q.append(root)
		while q:
			ql = len(q)
			l = []
			for i in range(ql):
				x = q.popleft()
				if x:
					l.append(x.data)
					q.append(x.left)
					q.append(x.right)
			if l:
				res.append(l)
		for i in range(len(res)):
			if i % 2 == 0:
				sum1 = sum1 + sum(res[i])
			else:
				sum2 = sum2 + sum(res[i])
		return sum1 - sum2


class Solution:

	def getLevelDiff(self, root):
		global s, s1
		s = 0
		s1 = 0

		def Sm(root, level):
			global s, s1
			if not root:
				return
			if level % 2 == 0:
				s = s + root.data
			else:
				s1 = s1 + root.data
			Sm(root.left, level + 1)
			Sm(root.right, level + 1)
		Sm(root, 1)
		return s1 - s


class Solution:

	def getLevelDiff(self, root):
		odd = even = 0
		level = 1
		q = [root]
		while q:
			size = len(q)
			for _ in range(size):
				node = q.pop(0)
				if level & 1:
					odd += node.data
				else:
					even += node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			level += 1
		return odd - even


class Solution:

	def getLevelDiff(self, root):
		i = 1
		even = []
		odd = []
		q = []
		q.append(root)
		while q:
			count = len(q)
			while count:
				temp = q.pop(0)
				if i % 2 != 0:
					odd.append(temp.data)
				else:
					even.append(temp.data)
				if temp.left:
					q.append(temp.left)
				if temp.right:
					q.append(temp.right)
				count -= 1
			i += 1
		return sum(odd) - sum(even)


class Solution:

	def getLevelDiff(self, root):

		def getdiff(root):
			if not root:
				return 0
			else:
				l = getdiff(root.left)
				r = getdiff(root.right)
				return root.data - l - r
		return getdiff(root)


class Solution:

	def getLevelDiff(self, root, l=0):
		if not root:
			return
		esum = 0
		osum = 0
		q = []
		l = 0
		q.append(root)
		while q:
			size = len(q)
			l += 1
			while size > 0:
				tmp = q.pop(0)
				if l % 2 == 0:
					esum += tmp.data
				else:
					osum += tmp.data
				if tmp.left:
					q.append(tmp.left)
				if tmp.right:
					q.append(tmp.right)
				size -= 1
		return osum - esum


class Solution:

	def getLevelDiff(self, root):
		if root is None:
			return 0
		que = [root]
		(odd, even, level) = (0, 0, 1)
		while que != []:
			temp = []
			for i in que:
				if level % 2 == 0:
					even += i.data
				else:
					odd += i.data
				if i.left:
					temp.append(i.left)
				if i.right:
					temp.append(i.right)
			level += 1
			que = temp
		return odd - even


class Solution:

	def getLevelDiff(self, root):
		q = []
		s1 = 0
		s2 = 0
		c = 0
		q.append(root)
		while q:
			sz = len(q)
			for i in range(sz):
				curr = q[0]
				q.pop(0)
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
				if c % 2 == 0:
					s1 += curr.data
				else:
					s2 += curr.data
			c += 1
		return s1 - s2


from collections import deque

class Solution:

	def getLevelDiff(self, root):
		if root is None:
			return 0
		ans = []
		cnt = 0
		sumo = 0
		sume = 0
		q = deque()
		q.append(root)
		while q:
			cnt = cnt + 1
			n = len(q)
			levelo = []
			levele = []
			for i in range(n):
				node = q.popleft()
				if cnt % 2 == 0:
					levele.append(node.data)
					sume = sume + node.data
				else:
					levelo.append(node.data)
					sumo = sumo + node.data
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
		return sumo - sume


class Solution:

	def getLevelDiff(self, root):
		flag = False
		queue = [root]
		odd = 0
		even = 0
		while queue:
			length = len(queue)
			for i in range(length):
				node = queue.pop(0)
				if node.left != None:
					queue.append(node.left)
				if node.right != None:
					queue.append(node.right)
				if flag:
					even += node.data
				else:
					odd += node.data
			flag = not flag
		return odd - even


class Solution:

	def getLevelDiff(self, root):
		if not root:
			return None
		even = []
		odd = []
		q = []
		l = 0
		q.append(root)
		while len(q) > 0:
			l += 1
			b = []
			li = []
			while len(q) > 0:
				node = q.pop(0)
				li.append(node.data)
				if node.left:
					b.append(node.left)
				if node.right:
					b.append(node.right)
			if l % 2 == 0:
				even.append(sum(li))
			else:
				odd.append(sum(li))
			q = b
		return sum(odd) - sum(even)