13. Maximum Non-Adjacent Nodes Sum
✅ GFG solution to the Maximum Non-Adjacent Nodes Sum problem: find maximum sum of nodes in a binary tree where no two adjacent nodes are selected using dynamic programming on trees. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
Given the root of a binary tree with integer values, your task is to select a subset of nodes such that the sum of their values is maximized, with the condition that no two selected nodes are directly connected. That is, if a node is included in the subset, neither its parent nor its children can be included.
A node and its immediate parent or children form adjacent pairs in the tree structure. The goal is to maximize the sum while respecting this non-adjacency constraint.
📘 Examples
Example 1
Input: root = [11, 1, 2]
Output: 11
Explanation: The maximum sum is obtained by selecting the node 11.Example 2
Input: root = [1, 2, 3, 4, N, 5, 6]
Output: 16
Explanation: The maximum sum is obtained by selecting the nodes 1, 4, 5 and 6,
which are not directly connected to each other. Their total sum is 16.🔒 Constraints
$1 \le \text{number of nodes} \le 10^4$
$1 \le \text{node.data} \le 10^5$
✅ My Approach
The optimal approach uses Dynamic Programming on Trees with a recursive strategy to compute two states for each node:
Tree DP with State Tracking
Define States:
For each node, maintain two values:
Include: Maximum sum when current node is included (children must be excluded).
Exclude: Maximum sum when current node is excluded (children can be either included or excluded).
Recursive Computation:
Base case: If node is NULL, return (0, 0) representing both states as 0.
For each node, recursively compute states for left and right children.
State Transition:
Include current node: Add node's value to the sum of excluded states of both children.
include = node->data + left_exclude + right_exclude
Exclude current node: Take maximum of both states for each child.
exclude = max(left_include, left_exclude) + max(right_include, right_exclude)
Return Result:
Return pair of (include, exclude) for each node.
Final answer is the maximum of both states at root.
Post-Order Traversal:
Process children before parent to ensure bottom-up computation.
Each node uses computed results from its subtrees.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n), where n is the number of nodes in the binary tree. We visit each node exactly once during the post-order traversal, performing constant time operations at each node.
Expected Auxiliary Space Complexity: O(h), where h is the height of the binary tree. This space is used by the recursion call stack. In the worst case of a skewed tree, h can be O(n), but for a balanced tree, it is O(log n).
🧑💻 Code (C++)
class Solution {
public:
int getMaxSum(Node* root) {
function<pair<int,int>(Node*)> dfs = [&](Node* node) -> pair<int,int> {
if (!node) return {0, 0};
auto [li, le] = dfs(node->left);
auto [ri, re] = dfs(node->right);
return {node->data + le + re, max(li, le) + max(ri, re)};
};
auto [inc, exc] = dfs(root);
return max(inc, exc);
}
};☕ Code (Java)
class Solution {
public int getMaxSum(Node root) {
int[] res = helper(root);
return Math.max(res[0], res[1]);
}
private int[] helper(Node node) {
if (node == null) return new int[]{0, 0};
int[] l = helper(node.left);
int[] r = helper(node.right);
int inc = node.data + l[1] + r[1];
int exc = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
return new int[]{inc, exc};
}
}🐍 Code (Python)
class Solution:
def getMaxSum(self, root):
def helper(node):
if not node: return (0, 0)
l = helper(node.left)
r = helper(node.right)
inc = node.data + l[1] + r[1]
exc = max(l) + max(r)
return (inc, exc)
return max(helper(root))🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated