Cohesity Interview: Binary Tree DP Problem (Maximum Non-Adjacent Subset Sum)

Cohesity Interview Experience – Binary Tree DP (Learning Moment) Recently, I interviewed with Cohesity and wanted to share one learning experience from the round. The interview started with a ~10 minu

Cohesity Interview Experience – Binary Tree DP (Learning Moment) Recently, I interviewed with Cohesity and wanted to share one learning experience from the round. The interview started with a ~10 minute discussion about my current work. We talked about my day-to-day responsibilities, the systems I work on, and the kind of problems I usually solve. The discussion was smooth and conversational. After that, the interviewer moved to a coding problem. ❓ Problem Asked Given a binary tree, find the maximum subset sum such that no two selected nodes are adjacent (i.e., you cannot pick both a parent and its child). This is essentially the “Maximum Sum of Non-Adjacent Nodes in a Binary Tree” problem (similar to House Robber III on LeetCode). 😅 What Happened Although I understood the problem constraints, I struggled to formulate the correct dynamic programming approach on a tree during the interview. I tried thinking in terms of traversal and greedy choices, but I couldn’t arrive at the clean solution within the time. In hindsight, the key was realizing that this is a tree DP problem, where for each node you need to track two states: when the node is included when the node is excluded ✅ Correct Approach (What I Learned) For each node: Include node → cannot include its children Exclude node → children can be included or excluded independently Return a pair {take, skip} for each node: take = node->val + left.skip + right.skip skip = max(left.take, left.skip) + max(right.take, right.skip) Final answer: max(root.take, root.skip) This solution runs in O(n) time and is very elegant once you see it. 📌 Takeaway This interview was a great reminder that: Tree problems often require DP with multiple states If a constraint says “cannot pick adjacent nodes”, think in terms of include / exclude Practicing classic patterns (Tree DP, DFS with return states) really matters Although I couldn’t solve it during the interview, it was a valuable learning experience and highlighted areas I’ve since focused on improving. Sharing this here so it helps others who might face a similar question 🙂