Given a binary tree with a value associated with each node, we need to choose a subset of these nodes such that sum of chosen nodes is maximum under a constraint that no two chosen node in subset should be directly connected that is, if we have taken a node in our sum then we can’t take its any children or parents in consideration and vice versa.
                                               
Example 1:
Input:
     11
    /  \
   1    2
Output: 11
Explanation: The maximum sum is sum of
node 11.
Example 2:
Input:
        1
      /   \
     2     3
    /     /  \
   4     5    6
Output: 16
Explanation: The maximum sum is sum of
nodes 1 4 5 6 , i.e 16. These nodes are
non adjacent.
Your Task:
You don't need to read input or print anything. You just have to complete function getMaxSum() which accepts root node of the tree as parameter and returns the maximum sum as described.
Expected Time Complexity: O(Number of nodes in the tree).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 ≤ Number of nodes in the tree ≤ 10000
1 ≤ Value of each node ≤ 100000

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
'''

class Solution:
    #Function to return the maximum sum of non-adjacent nodes.
    def getMaxSum(self,root):
        #code here

Solutions:
class Solution:

	def sol(self, root):
		if root is None:
			return [0, 0]
		leftAns = self.sol(root.left)
		rightAns = self.sol(root.right)
		a = root.data + leftAns[1] + rightAns[1]
		b = max(leftAns[0], leftAns[1]) + max(rightAns[0], rightAns[1])
		return [a, b]

	def getMaxSum(self, root):
		ans = self.sol(root)
		if ans[0] > ans[1]:
			return ans[0]
		return ans[1]


class Solution:

	def solve(self, root, F):
		if root is None:
			return 0
		if F.get(root):
			return F[root]
		incl = excl = 0
		incl = root.data
		if root.left:
			incl += self.solve(root.left.left, F)
			incl += self.solve(root.left.right, F)
		if root.right:
			incl += self.solve(root.right.left, F)
			incl += self.solve(root.right.right, F)
		excl += self.solve(root.left, F)
		excl += self.solve(root.right, F)
		F[root] = max(incl, excl)
		return F[root]

	def getMaxSum(self, root):
		F = {}
		return self.solve(root, F)


class Solution:

	def getMaxSum(self, root, dp={}):
		if root is None:
			return 0
		if dp.get(root) is not None:
			return dp[root]
		inc = root.data
		if root.left is not None:
			inc += self.getMaxSum(root.left.left, dp)
			inc += self.getMaxSum(root.left.right, dp)
		if root.right is not None:
			inc += self.getMaxSum(root.right.left, dp)
			inc += self.getMaxSum(root.right.right, dp)
		exc = self.getMaxSum(root.right, dp) + self.getMaxSum(root.left, dp)
		dp[root] = max(inc, exc)
		return dp[root]


class Solution:

	def getMaxSum(self, root):
		memo = {}

		def sm(r):
			if not r:
				return 0
			if r in memo:
				return memo[r]
			inc = r.data
			if r.left:
				inc += sm(r.left.left)
				inc += sm(r.left.right)
			if r.right:
				inc += sm(r.right.left)
				inc += sm(r.right.right)
			exc = sm(r.left) + sm(r.right)
			memo[r] = max(inc, exc)
			return memo[r]
		return sm(root)


class Solution:

	def getMaxSum(self, root):

		def answer(root):
			if root == None:
				return 0
			if g[root] != -1:
				return g[root]
			pick = root.data
			if root.left is not None:
				pick += answer(root.left.left)
				pick += answer(root.left.right)
			if root.right != None:
				pick += answer(root.right.left)
				pick += answer(root.right.right)
			nottake = answer(root.left) + answer(root.right)
			g[root] = max(pick, nottake)
			return max(pick, nottake)

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			g[root] = -1
			inorder(root.right)
		g = {}
		inorder(root)
		return answer(root)


class Solution:

	def getSum(self, root):
		if root is None:
			return [0, 0]
		sum1 = self.getSum(root.left)
		sum2 = self.getSum(root.right)
		sum = [0, 0]
		sum[0] = sum1[1] + sum2[1] + root.data
		sum[1] = max(sum1) + max(sum2)
		return sum

	def getMaxSum(self, root):
		sum = self.getSum(root)
		return max(sum)


class Solution:

	def __init__(self):
		self.res = [0, 0]

	def solve(self, root):
		if root == None:
			return [0, 0]
		left = self.solve(root.left)
		right = self.solve(root.right)
		res = [0, 0]
		res[1] = max(left) + max(right)
		res[0] = left[1] + right[1] + root.data
		return res

	def getMaxSum(self, root):
		ans = self.solve(root)
		return max(ans)


class Solution:

	def getMaxSum(self, root):
		return max(self.util(root))

	def util(self, root):
		if not root:
			return [0, 0]
		else:
			left = self.util(root.left)
			right = self.util(root.right)
			return [max(root.data + left[1] + right[1], left[0] + right[0]), left[0] + right[0]]


class Solution:

	def rec_sol(self, root, include_root, mp):
		if root in mp.keys() and mp[root][include_root] != -1:
			return mp[root][include_root]
		else:
			if include_root == 1:
				suma = root.data
				if root.left != None:
					suma = suma + self.rec_sol(root.left, 0, mp)
				if root.right != None:
					suma = suma + self.rec_sol(root.right, 0, mp)
			else:
				suma = 0
				if root.left != None:
					suma = suma + max(self.rec_sol(root.left, 1, mp), self.rec_sol(root.left, 0, mp))
				if root.right != None:
					suma = suma + max(self.rec_sol(root.right, 1, mp), self.rec_sol(root.right, 0, mp))
			if root not in mp.keys():
				mp[root] = [-1, -1]
			mp[root][include_root] = suma
			return suma

	def getMaxSum(self, root):
		mp = {}
		return max(self.rec_sol(root, 1, mp), self.rec_sol(root, 0, mp))


class Solution:

	def getMaxSum(self, root):

		def ans(root):
			if not root:
				return (0, 0)
			(ls, lcs) = ans(root.left)
			(rs, rcs) = ans(root.right)
			return (max(root.data + lcs + rcs, ls + rs), ls + rs)
		(maxans, cs) = ans(root)
		return maxans


class Solution:

	def getMaxSum(self, root):

		def sum_of_grandchildren(root, mp):
			s = 0
			if root.left:
				s += max_sum_util(root.left.left, mp) + max_sum_util(root.left.right, mp)
			if root.right:
				s += max_sum_util(root.right.left, mp) + max_sum_util(root.right.right, mp)
			return s

		def max_sum_util(root, mp):
			if root is None:
				return 0
			if root in mp:
				return mp[root]
			incl = root.data + sum_of_grandchildren(root, mp)
			excl = max_sum_util(root.left, mp) + max_sum_util(root.right, mp)
			mp[root] = max(incl, excl)
			return mp[root]
		if root is None:
			return 0
		mp = dict()
		return max_sum_util(root, mp)


class Solution:

	def getMaxSum(self, root):

		def max_sum_util(root):
			if root is None:
				return [0, 0]
			sum1 = max_sum_util(root.left)
			sum2 = max_sum_util(root.right)
			summ = [0, 0]
			summ[0] = root.data + sum1[1] + sum2[1]
			summ[1] = max(sum1[0], sum1[1]) + max(sum2[0], sum2[1])
			return summ
		return max(max_sum_util(root))


def solve(root):
	if root is None:
		return (0, 0)
	(lf, ls) = solve(root.left)
	(rf, rs) = solve(root.right)
	resf = root.data + ls + rs
	ress = max(lf, ls) + max(rf, rs)
	return (resf, ress)

class Solution:

	def getMaxSum(self, root):
		(rf, rs) = solve(root)
		ans = max(rf, rs)
		return ans


from collections import defaultdict as dict

class Solution:

	def getMaxSum(self, root):
		memo = dict(int)

		def rec(root):
			if root == None:
				return 0
			if root in memo:
				return memo[root]
			take = root.data
			if root.left:
				take += rec(root.left.left) + rec(root.left.right)
			if root.right:
				take += rec(root.right.left) + rec(root.right.right)
			notTake = rec(root.left) + rec(root.right)
			maxi = max(take, notTake)
			memo[root] = maxi
			return memo[root]
		ans = rec(root)
		return ans


from functools import lru_cache

class Solution:

	def getMaxSum(self, root):

		@lru_cache(None)
		def _backtrack(node, sel) -> int:
			if not node:
				return 0
			node_selected = node.data
			node_skipped = 0
			for child_node in [node.left, node.right]:
				node_selected += max(0, _backtrack(child_node, False))
				node_skipped += max(0, _backtrack(child_node, True))
			if sel:
				return max(node_selected, node_skipped)
			return node_skipped
		result = max(_backtrack(root, False), _backtrack(root, True))
		return result if result > 0 else 0


def get_sum(root, hash_map):
	if root == None:
		return
	elif root.left == None and root.right == None:
		hash_map[root] = [root.data, 0]
	else:
		get_sum(root.left, hash_map)
		get_sum(root.right, hash_map)
		if root.left:
			l = hash_map[root.left]
		else:
			l = [0, 0]
		if root.right:
			r = hash_map[root.right]
		else:
			r = [0, 0]
		hash_map[root] = [root.data + l[1] + r[1], max(l) + max(r)]

class Solution:

	def getMaxSum(self, root):
		hash_map = {}
		if root == None:
			return 0
		else:
			get_sum(root, hash_map)
		result = -9999999
		for key in hash_map:
			result = max(result, max(hash_map[key]))
		return result


class Solution:

	def solve(self, root):
		if root is None:
			return (0, 0)
		(leftin, leftex) = self.solve(root.left)
		(rightin, rightex) = self.solve(root.right)
		return (root.data + leftex + rightex, max(leftin, leftex) + max(rightin, rightex))

	def getMaxSum(self, root):
		(ansin, ansex) = self.solve(root)
		return max(ansin, ansex)


class Solution:

	def getMaxSum(self, root):
		dp = {}

		def getsum(root):
			if not root:
				return 0
			if root in dp:
				return dp[root]
			include = root.data
			if root.left:
				include += getsum(root.left.left)
				include += getsum(root.left.right)
			if root.right:
				include += getsum(root.right.left)
				include += getsum(root.right.right)
			exclude = getsum(root.left) + getsum(root.right)
			dp[root] = max(include, exclude)
			return dp[root]
		return getsum(root)


from collections import defaultdict

class Solution:

	def max_sum(self, root, ignore, dp):
		if root == None:
			return 0
		if ignore == 1:
			return self.max_sum(root.left, 0, dp) + self.max_sum(root.right, 0, dp)
		if root in dp:
			return dp[root]
		inc = root.data + self.max_sum(root.left, 1, dp) + self.max_sum(root.right, 1, dp)
		exc = self.max_sum(root.left, 0, dp) + self.max_sum(root.right, 0, dp)
		dp[root] = max(inc, exc)
		return dp[root]

	def getMaxSum(self, root):
		dp = {}
		x = self.max_sum(root, 0, dp)
		return x


class Solution:

	def getMaxSum(self, root):

		def dfs(root):
			if not root:
				return (0, 0)
			(leftincl, leftexcl) = dfs(root.left)
			(rightincl, rightexcl) = dfs(root.right)
			return (root.data + leftexcl + rightexcl, max(leftincl, leftexcl) + max(rightincl, rightexcl))
		(ansincl, ansexcl) = dfs(root)
		return max(ansincl, ansexcl)


class Solution:

	def getMaxSum(self, root):

		def dfs(node):
			if not node:
				return [0, 0]
			left = dfs(node.left)
			right = dfs(node.right)
			rob = node.data + left[1] + right[1]
			notRob = max(left) + max(right)
			return [rob, notRob]
		return max(dfs(root))


class Solution:

	def Solve(self, root, memory):
		if root == None:
			return 0
		if root not in memory:
			include = root.data
			if root.left:
				include += self.Solve(root.left.left, memory) + self.Solve(root.left.right, memory)
			if root.right:
				include += self.Solve(root.right.left, memory) + self.Solve(root.right.right, memory)
			exclude = self.Solve(root.left, memory) + self.Solve(root.right, memory)
			memory[root] = max(include, exclude)
		return memory[root]

	def getMaxSum(self, root):
		memory = dict()
		return self.Solve(root, memory)


class Solution:
	umap = {}

	def getMaxSum(self, root):
		if root == None:
			return 0
		if root in self.umap:
			return self.umap[root]
		inc = root.data
		if root.left:
			inc = inc + self.getMaxSum(root.left.left) + self.getMaxSum(root.left.right)
		if root.right:
			inc = inc + self.getMaxSum(root.right.left) + self.getMaxSum(root.right.right)
		exc = self.getMaxSum(root.right) + self.getMaxSum(root.left)
		self.umap[root] = max(inc, exc)
		return max(inc, exc)


class Solution:

	def getMaxSum(self, root):

		def rec(root):
			if root is None:
				return [0, 0]
			left = rec(root.left)
			right = rec(root.right)
			first = root.data + left[1] + right[1]
			second = max(left[0], left[1]) + max(right[0], right[1])
			return [first, second]
		ans = rec(root)
		return max(ans[0], ans[1])


class Solution:

	def getMaxSum(self, root):

		def maxsum(root):
			if root == None:
				return [0, 0]
			x = maxsum(root.left)
			y = maxsum(root.right)
			return [root.data + x[1] + y[1], max(x) + max(y)]
		return max(maxsum(root))


class Solution:

	def helper(self, root):
		if not root:
			return (0, 0)
		left = self.helper(root.left)
		right = self.helper(root.right)
		return (root.data + left[1] + right[1], max(left) + max(right))

	def getMaxSum(self, root):
		ans = self.helper(root)
		return max(ans)


from collections import deque

class Solution:

	def getMaxSum(self, root):
		ans = getSum(root)
		return max(ans[0], ans[1])

def getSum(root):
	if root == None:
		return [0, 0]
	left = getSum(root.left)
	right = getSum(root.right)
	exclude = max(left[0], left[1]) + max(right[0], right[1])
	include = left[1] + right[1] + root.data
	return [include, exclude]


class Solution:

	def getMaxSum(self, root):
		mp = dict()

		def findsol(root):
			if root == None:
				return 0
			if root in mp:
				return mp[root]
			inc = root.data
			if root.left:
				inc += findsol(root.left.left)
				inc += findsol(root.left.right)
			if root.right:
				inc += findsol(root.right.left)
				inc += findsol(root.right.right)
			exc = findsol(root.right) + findsol(root.left)
			ans = max(inc, exc)
			if root not in mp:
				mp[root] = ans
			return ans
		return findsol(root)


from collections import defaultdict as dd

def adsum(head, par, ans):
	if head:
		if par is False:
			a = head.data
			if head.left in ans and True in ans[head.left]:
				a1 = ans[head.left][True]
			else:
				ans[head.left][True] = adsum(head.left, True, ans)
				a1 = ans[head.left][True]
			if head.right in ans and True in ans[head.right]:
				a2 = ans[head.right][True]
			else:
				ans[head.right][True] = adsum(head.right, True, ans)
				a2 = ans[head.right][True]
			if head.left in ans and False in ans[head.left]:
				a3 = ans[head.left][False]
			else:
				ans[head.left][False] = adsum(head.left, False, ans)
				a3 = ans[head.left][False]
			if head.right in ans and False in ans[head.right]:
				a4 = ans[head.right][False]
			else:
				ans[head.right][False] = adsum(head.right, False, ans)
				a4 = ans[head.right][False]
			return max(a + a1 + a2, a3 + a4)
		else:
			if head.left in ans and False in ans[head.left]:
				a3 = ans[head.left][False]
			else:
				ans[head.left][False] = adsum(head.left, False, ans)
				a3 = ans[head.left][False]
			if head.right in ans and False in ans[head.right]:
				a4 = ans[head.right][False]
			else:
				ans[head.right][False] = adsum(head.right, False, ans)
				a4 = ans[head.right][False]
			return a3 + a4
	return 0

class Solution:

	def getMaxSum(self, root):
		ans = dd(dict)
		return adsum(root, False, ans)


class Solution:

	def __init__(self):
		self.ans = 0

	def getMaxSum(self, root):
		hmap = {}

		def solve(root):
			if not root:
				return 0
			if root not in hmap:
				inc = root.data
				if root.left:
					inc += solve(root.left.left)
					inc += solve(root.left.right)
				if root.right:
					inc += solve(root.right.left)
					inc += solve(root.right.right)
				exc = solve(root.left) + solve(root.right)
				hmap[root] = max(inc, exc)
			return hmap[root]
		return solve(root)


class Solution:

	def maxSum(self, root, dp):
		if root is None:
			return 0
		if root in dp:
			return dp[root]
		incl = root.data
		if root.left:
			incl += self.maxSum(root.left.left, dp)
			incl += self.maxSum(root.left.right, dp)
		if root.right:
			incl += self.maxSum(root.right.left, dp)
			incl += self.maxSum(root.right.right, dp)
		excl = self.maxSum(root.left, dp) + self.maxSum(root.right, dp)
		dp[root] = max(incl, excl)
		return dp[root]

	def getMaxSum(self, root):
		dp = {}
		out = self.maxSum(root, dp)
		return out


class Solution:

	def getMaxSum(self, root):

		def dfs(root):
			if not root:
				return (0, 0)
			left = dfs(root.left)
			right = dfs(root.right)
			return (max(root.data + left[1] + right[1], left[0] + right[0]), left[0] + right[0])
		return max(dfs(root))


class Solution:

	def getMaxSum1(self, root, dp):
		if root == None:
			return 0
		if root in dp:
			return dp[root]
		sum1 = self.getMaxSum1(root.left, dp) + self.getMaxSum1(root.right, dp)
		sum2 = root.data
		if root.left != None:
			sum2 += self.getMaxSum1(root.left.left, dp) + self.getMaxSum1(root.left.right, dp)
		if root.right != None:
			sum2 += self.getMaxSum1(root.right.left, dp) + self.getMaxSum1(root.right.right, dp)
		dp[root] = max(sum1, sum2)
		return max(sum1, sum2)

	def getMaxSum(self, root):
		dp = {}
		ans = self.getMaxSum1(root, dp)
		return ans


class Solution:

	def max_sum(self, root):
		if not root:
			return (0, 0)
		(no_root_l, root_l) = self.max_sum(root.left)
		(no_root_r, root_r) = self.max_sum(root.right)
		root_sum_max = max(root.data, root.data + no_root_l, root.data + no_root_r, root.data + no_root_r + no_root_l)
		no_root_sum_max = max(root_l, root_r, root_l + root_r, no_root_l + no_root_r, root_l + no_root_r, root_r + no_root_l)
		return (no_root_sum_max, root_sum_max)

	def getMaxSum(self, root):
		return max(self.max_sum(root))


class Solution:

	def getMaxSum(self, root):
		return dfs(root, {})

def dfs(n, memo, skip=False):
	if not n:
		return 0
	if (n, skip) in memo:
		return memo[n, skip]
	v = 0 if skip else n.data
	incl = 0
	if not skip:
		incl = n.data + dfs(n.left, memo, True) + dfs(n.right, memo, True)
	excl = dfs(n.left, memo) + dfs(n.right, memo)
	memo[n, skip] = max(incl, excl)
	return memo[n, skip]


class Solution:

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

	def getMaxSum(self, root):
		if root == None:
			return 0
		if root in self.d:
			return self.d[root]
		include = root.data
		if root.left != None:
			include += self.getMaxSum(root.left.left)
			include += self.getMaxSum(root.left.right)
		if root.right != None:
			include += self.getMaxSum(root.right.left)
			include += self.getMaxSum(root.right.right)
		exclude = self.getMaxSum(root.left) + self.getMaxSum(root.right)
		self.d[root] = max(include, exclude)
		return self.d[root]


class Solution:

	def func(self, root):
		if root is None:
			return [0, 0]
		l = self.func(root.left)
		r = self.func(root.right)
		left = root.data + l[1] + r[1]
		right = max(l[0], l[1]) + max(r[0], r[1])
		return [left, right]

	def getMaxSum(self, root):
		x = self.func(root)
		return max(x[0], x[1])


class Solution:

	def getMaxSum(self, root):
		self.map = {}
		return self.func(root)

	def func(self, root):
		if not root:
			return 0
		if root in self.map:
			return self.map[root]
		if root.left and root.right:
			a = root.data + self.func(root.left.left) + self.func(root.left.right) + self.func(root.right.left) + self.func(root.right.right)
		elif root.left:
			a = root.data + self.func(root.left.left) + self.func(root.left.right)
		elif root.right:
			a = root.data + self.func(root.right.left) + self.func(root.right.right)
		else:
			a = root.data
		b = self.func(root.left) + self.func(root.right)
		ans = max(a, b)
		self.map[root] = ans
		return ans


class Solution:

	def solve(self, root, memo):
		if root == None:
			return 0
		if memo.get(root):
			return memo.get(root)
		(including, excluding) = (root.data, 0)
		if root.left:
			including += self.solve(root.left.left, memo)
			including += self.solve(root.left.right, memo)
		if root.right:
			including += self.solve(root.right.left, memo)
			including += self.solve(root.right.right, memo)
		excluding += self.solve(root.left, memo)
		excluding += self.solve(root.right, memo)
		memo[root] = max(including, excluding)
		return memo[root]

	def getMaxSum(self, root):
		memo = {}
		return self.solve(root, memo)


from collections import defaultdict

class Solution:
	dp = defaultdict(int)

	def getMaxSum(self, root):
		if root == None:
			return 0
		if root in self.dp:
			return self.dp[root]
		inc_sum = root.data
		if root.left:
			inc_sum += self.getMaxSum(root.left.left) + self.getMaxSum(root.left.right)
		if root.right:
			inc_sum += self.getMaxSum(root.right.left) + self.getMaxSum(root.right.right)
		exc_sum = 0
		exc_sum += self.getMaxSum(root.left)
		exc_sum += self.getMaxSum(root.right)
		maxSum = max(inc_sum, exc_sum)
		self.dp[root] = maxSum
		return self.dp[root]


from collections import defaultdict

class Solution:
	lookup = defaultdict(int)

	def getOptimalSum(self, root):
		if root == None:
			return 0
		if root in self.lookup:
			return self.lookup[root]
		(gcLL, gcLR) = (0, 0)
		(gcRL, gcRR) = (0, 0)
		if root.left:
			gcLL = self.getOptimalSum(root.left.left)
			gcLR = self.getOptimalSum(root.left.right)
		if root.right:
			gcRL = self.getOptimalSum(root.right.left)
			gcRR = self.getOptimalSum(root.right.right)
		include = root.data + gcLL + gcLR + gcRL + gcRR
		cL = self.getOptimalSum(root.left)
		cR = self.getOptimalSum(root.right)
		exclude = cL + cR
		self.lookup[root] = max(include, exclude)
		return self.lookup[root]

	def getMaxSum(self, root):
		return self.getOptimalSum(root)


class Solution:

	def getMaxSum(self, root):

		def helper(root):
			if root == None:
				return [0, 0]
			[leftSumIncluding, leftSumExcluding] = helper(root.left)
			[rightSumIncluding, rightSumExcluding] = helper(root.right)
			maxSumIncluding = root.data + leftSumExcluding + rightSumExcluding
			maxSumExcluding = max(leftSumIncluding, leftSumExcluding) + max(rightSumIncluding, rightSumExcluding)
			return [maxSumIncluding, maxSumExcluding]
		return max(helper(root))


class Solution:

	def getMaxSum(self, root):

		def tree(root, dp):
			if root is None:
				return 0
			if root in dp:
				return dp[root]
			pick = root.data
			if root.left:
				pick += tree(root.left.left, dp)
				pick += tree(root.left.right, dp)
			if root.right:
				pick += tree(root.right.left, dp)
				pick += tree(root.right.right, dp)
			nonpick = tree(root.left, dp) + tree(root.right, dp)
			dp[root] = max(pick, nonpick)
			return dp[root]
		dp = {}
		return tree(root, dp)


class Solution:

	def getMaxSum(self, root):

		def helper(root):
			if root == None:
				return [0, 0]
			leftAns = helper(root.left)
			rightAns = helper(root.right)
			maxSumIncluding = root.data + leftAns[1] + rightAns[1]
			maxSumExcluding = max(leftAns[0], leftAns[1]) + max(rightAns[0], rightAns[1])
			return [maxSumIncluding, maxSumExcluding]
		return max(helper(root))


class Solution:

	def solve(self, root):
		if root is None:
			return (0, 0)
		l_ans = self.solve(root.left)
		r_ans = self.solve(root.right)
		inc = root.data + l_ans[1] + r_ans[1]
		exc = max(l_ans) + max(r_ans)
		return (inc, exc)

	def getMaxSum(self, root):
		ans = self.solve(root)
		return max(ans)


class Solution:
	dic = {}

	def getMaxSum(self, root):
		if not root:
			return 0
		if root in self.dic:
			return self.dic[root]
		l = 0
		r = 0
		if root.left:
			l = self.getMaxSum(root.left.left) + self.getMaxSum(root.left.right)
		if root.right:
			r = self.getMaxSum(root.right.left) + self.getMaxSum(root.right.right)
		maxi = l + r + root.data
		self.dic[root] = max(maxi, self.getMaxSum(root.left) + self.getMaxSum(root.right))
		return self.dic[root]


class Solution:

	def getMaxSum(self, root):
		hm = {}

		def solve(root):
			if root == None:
				return 0
			if root in hm:
				return hm[root]
			include = exclude = 0
			include += root.data
			if root.left:
				include += solve(root.left.left)
				include += solve(root.left.right)
			if root.right:
				include += solve(root.right.left)
				include += solve(root.right.right)
			exclude += solve(root.left)
			exclude += solve(root.right)
			hm[root] = max(include, exclude)
			return hm[root]
		return solve(root)


class Solution:

	def solve(self, root, dp):
		if root == None:
			return 0
		if root in dp:
			return dp[root]
		incl = root.data
		if root.left != None:
			incl += self.solve(root.left.left, dp)
			incl += self.solve(root.left.right, dp)
		if root.right != None:
			incl += self.solve(root.right.right, dp)
			incl += self.solve(root.right.left, dp)
		excl = self.solve(root.left, dp) + self.solve(root.right, dp)
		dp[root] = max(incl, excl)
		return dp[root]

	def getMaxSum(self, root):
		dp = {}
		return self.solve(root, dp)


class Solution:

	def getMaxSum(self, root):
		res = self.bestAlternateSum(root)
		return max(res[0], res[1])

	def bestAlternateSum(self, root):
		if not root:
			return (0, 0)
		sum1 = self.bestAlternateSum(root.left)
		sum2 = self.bestAlternateSum(root.right)
		include_sum = sum1[1] + sum2[1] + root.data
		exclude_sum = max(sum1[0], sum1[1]) + max(sum2[0], sum2[1])
		return (include_sum, exclude_sum)


class Solution:
	res = {}

	def getMaxSum(self, root):
		return self.bestAlternateSum(root)

	def bestAlternateSum(self, root):
		if not root:
			return 0
		if root in Solution.res:
			return Solution.res[root]
		sum = root.data
		if root.left:
			sum += self.bestAlternateSum(root.left.left)
			sum += self.bestAlternateSum(root.left.right)
		if root.right:
			sum += self.bestAlternateSum(root.right.left)
			sum += self.bestAlternateSum(root.right.right)
		lsum = self.bestAlternateSum(root.left)
		rsum = self.bestAlternateSum(root.right)
		ans = max(sum, lsum + rsum)
		Solution.res[root] = ans
		return ans


class Solution:

	def grandChildrenSum(self, root, d):
		sm = 0
		if root.left:
			sm += self.getMaxSumUtil(root.left.left, d) + self.getMaxSumUtil(root.left.right, d)
		if root.right:
			sm += self.getMaxSumUtil(root.right.left, d) + self.getMaxSumUtil(root.right.right, d)
		return sm

	def getMaxSumUtil(self, root, d):
		if not root:
			return 0
		if d.get(root):
			return d[root]
		incl = root.data + self.grandChildrenSum(root, d)
		excl = self.getMaxSumUtil(root.left, d) + self.getMaxSumUtil(root.right, d)
		d[root] = max(incl, excl)
		return d[root]

	def getMaxSum(self, root):
		if not root:
			return 0
		d = {}
		return self.getMaxSumUtil(root, d)


class Solution:

	def solve(self, root):
		if root == None:
			return [0, 0]
		left = self.solve(root.left)
		right = self.solve(root.right)
		child = left[0] + right[0]
		grandchild = left[1] + right[1]
		second = left[0] + right[0]
		second = max(second, left[1] + right[0])
		second = max(second, left[1] + right[1])
		second = max(second, left[0] + right[1])
		return [root.data + grandchild, second]

	def getMaxSum(self, root):
		x = self.solve(root)
		return max(x[0], x[1])


class Solution:

	def findmax(self, root):
		if root == None:
			return [0, 0]
		(prev_left, cur_left) = self.findmax(root.left)
		(prev_right, cur_right) = self.findmax(root.right)
		arr = [cur_left + cur_right]
		arr.append(max(arr[0], prev_left + prev_right + root.data))
		return arr

	def getMaxSum(self, root):
		return max(self.findmax(root))


from collections import Counter

class Solution:

	def getMaxSum(self, root):
		dp1 = Counter()
		dp2 = Counter()
		node = root

		def dfs(root):
			if not root:
				return
			dfs(root.left)
			dfs(root.right)
			sum1 = dp2[root.left] + dp2[root.right]
			sum2 = max(dp2[root.left], dp1[root.left]) + max(dp2[root.right], dp1[root.right])
			dp1[root] = root.data + sum1
			dp2[root] = sum2
		dfs(node)
		return max(max(dp1.values()), max(dp2.values()))


import collections

class Solution:

	def getMaxSum(self, root):

		def helper(node):
			if node is None:
				return (0, 0)
			if node.left is None and node.right is None:
				return (node.data, 0)
			(left_include, left_exclude) = helper(node.left)
			(right_include, right_exclude) = helper(node.right)
			include = node.data + left_exclude + right_exclude
			exclude = max(left_include, left_exclude) + max(right_include, right_exclude)
			return (include, exclude)
		return max(helper(root))


import collections

class Solution:

	def getMaxSum(self, root):

		def helper(node):
			if node is None:
				return (0, 0)
			if node.left is None and node.right is None:
				return (node.data, 0)
			(li, le) = helper(node.left)
			(ri, re) = helper(node.right)
			include = node.data + le + re
			exclude = max(li, le) + max(ri, re)
			return (include, exclude)
		return max(helper(root))


class Solution:

	def getMaxSum(self, root):
		if root == None:
			return 0
		return max(self.path(root))

	def path(self, root):
		if root == None:
			return [0, 0]
		l = self.path(root.left)
		r = self.path(root.right)
		return [root.data + l[1] + r[1], max(l[0], l[1]) + max(r[0], r[1])]


class Solution:

	def getMaxSum(self, root):
		self.di = dict()

		def solve(root):
			if not root:
				return 0
			if root in self.di:
				return self.di[root]
			(take, not_take) = [0] * 2
			take = root.data
			if root.left:
				take += solve(root.left.left) + solve(root.left.right)
			if root.right:
				take += solve(root.right.left) + solve(root.right.right)
			not_take = solve(root.left) + solve(root.right)
			self.di[root] = max(take, not_take)
			return max(take, not_take)
		return solve(root)


class Solution:

	def __init__(self):
		self.d = dict()

	def getMaxSum(self, root):
		if not root:
			return
		skipv = 0
		if root.right:
			skipv = skipv + self.getMaxSum(root.right)
		if root.left:
			skipv = skipv + self.getMaxSum(root.left)
		keepv = root.data
		if root.right:
			if root.right.right:
				keepv = keepv + self.d[root.right.right]
			if root.right.left:
				keepv = keepv + self.d[root.right.left]
		if root.left:
			if root.left.right:
				keepv = keepv + self.d[root.left.right]
			if root.left.left:
				keepv = keepv + self.d[root.left.left]
		self.d[root] = max(keepv, skipv)
		return self.d[root]


class Solution:

	def getMaxSum(self, root):
		hash = {}

		def fun(root):
			if root == None:
				return 0
			if root in hash:
				return hash[root]
			(l, r) = (root.data, 0)
			if root.left:
				l += fun(root.left.left) + fun(root.left.right)
			if root.right:
				l += fun(root.right.right) + fun(root.right.left)
			r += fun(root.left) + fun(root.right)
			t = max(l, r)
			hash[root] = t
			return t
		return fun(root)


class Solution:

	def getMaxSum(self, root):

		def solve(root):
			if not root:
				return [0, 0]
			(left_in, left_ex) = solve(root.left)
			(right_in, right_ex) = solve(root.right)
			return [right_ex + left_ex + root.data, max(left_in, left_ex) + max(right_in, right_ex)]
		ans = solve(root)
		return max(ans[0], ans[1])


class Solution:

	def getMaxSum(self, root):
		dp = {}

		def solve(root=root):
			nonlocal dp
			if not root:
				return 0
			if root in dp:
				return dp[root]
			incl = root.data
			if root.left:
				incl += sum(map(solve, [root.left.left, root.left.right]))
			if root.right:
				incl += sum(map(solve, [root.right.left, root.right.right]))
			excl = sum(map(solve, [root.left, root.right]))
			dp[root] = max(incl, excl)
			return dp[root]
		return solve()


class Solution:
	d = {}

	def getMaxSum(self, root):

		def helper(node):
			if node == None:
				return 0
			if node in self.d.keys():
				return self.d[node]
			include = node.data
			if node.right:
				include += helper(node.right.right)
				include += helper(node.right.left)
			if node.left:
				include += helper(node.left.right)
				include += helper(node.left.left)
			exclude = helper(node.left) + helper(node.right)
			self.d[node] = max(include, exclude)
			return self.d[node]
		return helper(root)


class Solution:

	def maxSumHelper(self, root):
		if root == None:
			sum = [0, 0]
			return sum
		sum1 = self.maxSumHelper(root.left)
		sum2 = self.maxSumHelper(root.right)
		sum = [0, 0]
		sum[0] = sum1[1] + sum2[1] + root.data
		sum[1] = max(sum1[0], sum1[1]) + max(sum2[0], sum2[1])
		return sum

	def getMaxSum(self, root):
		res = self.maxSumHelper(root)
		return max(res[0], res[1])


class Solution:

	def getMaxSum(self, root):

		def solve_gc(root, mp):
			s = 0
			if root.left:
				s += solve(root.left.left, mp) + solve(root.left.right, mp)
			if root.right:
				s += solve(root.right.left, mp) + solve(root.right.right, mp)
			return s

		def solve(root, mp):
			if root == None:
				return 0
			if root in mp:
				return mp[root]
			inc = root.data + solve_gc(root, mp)
			exc = solve(root.left, mp) + solve(root.right, mp)
			mp[root] = max(inc, exc)
			return mp[root]

		def starter(root):
			if root == None:
				return 0
			mp = dict()
			return solve(root, mp)
		return starter(root)


class Solution:

	def getMaxSum(self, root):
		dp1 = {None: 0}
		dp2 = {None: 0}
		ans = float('-inf')

		def dfs(node):
			nonlocal ans
			if node:
				dfs(node.left)
				dfs(node.right)
				dp1[node] = node.data + dp2[node.left] + dp2[node.right]
				dp2[node] = max(dp1[node.left], dp2[node.left]) + max(dp1[node.right], dp2[node.right])
				ans = max(ans, dp1[node], dp2[node])
		dfs(root)
		return ans


class Solution:

	def getMaxSum(self, root):

		def solve(root):
			if root == None:
				return [0, 0]
			lft = solve(root.left)
			rt = solve(root.right)
			return [lft[1] + rt[1] + root.data, max(lft) + max(rt)]
		ans = solve(root)
		return max(ans[0], ans[1])


class Solution:

	def getMaxSum(self, root):

		def trvrse(node):
			if not node:
				return [0, 0]
			lans = trvrse(node.left)
			rans = trvrse(node.right)
			res = [0, 0]
			res[0] = lans[1] + rans[1] + node.data
			res[1] = max(lans[0], lans[1]) + max(rans[0], rans[1])
			return res
		sol = trvrse(root)
		return max(sol[0], sol[1])


class Solution:

	def getMaxSum(self, root):
		mp = {}
		return self.rec(root, mp)

	def rec(self, root, mp):
		if root is None:
			return 0
		if root in mp:
			return mp[root]
		incl = root.data
		if root.left:
			incl += self.rec(root.left.left, mp)
			incl += self.rec(root.left.right, mp)
		if root.right:
			incl += self.rec(root.right.left, mp)
			incl += self.rec(root.right.right, mp)
		excl = self.rec(root.left, mp) + self.rec(root.right, mp)
		mp[root] = max(incl, excl)
		return mp[root]


class Solution:

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

	def getMaxSum(self, root):
		if root == None:
			return 0
		if self.dp.get(root):
			return self.dp[root]
		inc = root.data
		if root.left:
			inc += self.getMaxSum(root.left.left)
			inc += self.getMaxSum(root.left.right)
		if root.right:
			inc += self.getMaxSum(root.right.left)
			inc += self.getMaxSum(root.right.right)
		exe = self.getMaxSum(root.left) + self.getMaxSum(root.right)
		self.dp[root] = max(inc, exe)
		return self.dp[root]


class Solution:

	def getMaxSum(self, root):
		q = max(self.solve(root)[0], self.solve(root)[1])
		return q

	def solve(self, root):
		if root == None:
			return (0, 0)
		(al, bl) = self.solve(root.left)
		(ar, br) = self.solve(root.right)
		p = root.data + bl + br
		q = max(al, bl) + max(ar, br)
		return (p, q)


class Solution:

	def solve(self, node):
		if not node:
			return (0, 0)
		(leftIn, leftEx) = self.solve(node.left)
		(rightIn, rightEx) = self.solve(node.right)
		curIn = node.data + leftEx + rightEx
		curEx = max(leftIn, leftEx) + max(rightIn, rightEx)
		return (curIn, curEx)

	def getMaxSum(self, node):
		if node == None:
			return
		(included, excluded) = self.solve(node)
		return max(included, excluded)


class Solution:

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

	def getMaxSum(self, root):
		if not root:
			return 0
		if root in self.dp_dict:
			return self.dp_dict[root]
		ls = self.getMaxSum(root.left)
		rs = self.getMaxSum(root.right)
		s1 = ls + rs
		s2 = root.data
		if root.left:
			s2 += self.getMaxSum(root.left.left)
			s2 += self.getMaxSum(root.left.right)
		if root.right:
			s2 += self.getMaxSum(root.right.left)
			s2 += self.getMaxSum(root.right.right)
		self.dp_dict[root] = max(s1, s2)
		return max(s1, s2)


from functools import lru_cache

class Solution:

	def getMaxSum(self, root):

		def sumi(node, taken, dp={}):
			if not node:
				return 0
			if (node, taken) in dp:
				return dp[node, taken]
			if taken:
				dp[node, taken] = sumi(node.left, False, dp) + sumi(node.right, False, dp)
				return dp[node, taken]
			dp[node, taken] = max(node.data + sumi(node.left, True, dp) + sumi(node.right, True), sumi(node.left, False, dp) + sumi(node.right, False, dp))
			return dp[node, taken]
		return sumi(root, False)


import sys

class Solution:

	def treeSum_v1(self, root, parent, adj, tsum, skip):
		if root:
			if not skip:
				if root.data not in adj:
					adj[root.data] = 0
				if parent:
					adj[root.data] += parent.data
				if root.left:
					adj[root.data] += root.left.data
				if root.right:
					adj[root.data] += root.right.data
				tsum[0] += root.data
				self.treeSum(root.left, root, adj, tsum, skip ^ 1)
				self.treeSum(root.right, root, adj, tsum, skip ^ 1)
			else:
				tsum[0] += root.data
				tsum[1] += root.data
				self.treeSum(root.left, root, adj, tsum, skip ^ 1)
				self.treeSum(root.left, root, adj, tsum, skip ^ 1)

	def treeSum(self, root, tsum, skip):
		if root:
			if not skip:
				lsum = self.treeSum(root.left, tsum, skip ^ 1)
				rsum = self.treeSum(root.right, tsum, skip ^ 1)
				tsum[0] += root.data
			else:
				self.treeSum(root.left, tsum, skip ^ 1)
				self.treeSum(root.right, tsum, skip ^ 1)
		return tsum[0]

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

	def getMaxSum(self, root):
		if root is None:
			return 0
		if root in self.m:
			return self.m[root]
		exc = 0
		inc = root.data
		if root.left:
			inc += self.getMaxSum(root.left.left)
			inc += self.getMaxSum(root.left.right)
		if root.right:
			inc += self.getMaxSum(root.right.right)
			inc += self.getMaxSum(root.right.left)
		exc = self.getMaxSum(root.left) + self.getMaxSum(root.right)
		ans = max(inc, exc)
		self.m[root] = ans
		return ans


class Solution:

	def getMaxSum(self, root):

		def g_max(root):
			if root:
				(l1, l2) = g_max(root.left)
				(r1, r2) = g_max(root.right)
				return (root.data + l2 + r2, max(l1, l2) + max(r1, r2))
			return (0, 0)
		(ans1, ans2) = g_max(root)
		return max(ans1, ans2)


class Solution:

	def getMaxSum(self, root):

		def helper(node):
			summ = [0, 0]
			if not node:
				return summ
			summ1 = helper(node.left)
			summ2 = helper(node.right)
			summ[0] = summ1[1] + summ2[1] + node.data
			summ[1] = max(summ1) + max(summ2)
			return summ
		return max(helper(root))