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 🙂