← Adobe Interview Insights

Adobe·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Did a coding round for a Software Engineer role at Adobe and got hit with the binary tree maximum path sum problem. Pretty classic but the solution has a subtle twist that's easy to fumble if you haven't seen it before.

Questions Asked (1)

Q1

Given the root of a binary tree, find the maximum path sum where a path can start and end at any node and does not need to pass through the root.

Algorithms & Data Structures
Author's notes

The key thing that trips people up here is that you're solving two problems at once.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a post-order DFS that returns the maximum downward path sum from each node, while maintaining a global maximum that considers paths bending through the node (left + node + right). At each node, compute the best single-branch contribution and update the global answer with the best bent path.

Pro tip: Explicitly handle negative values by clamping branch contributions to 0 (i.e., ignore negative subtrees), and mention that this is a classic 'max gain' tree DP pattern often asked at Adobe.

1. Clarify the problem and constraints

Confirm that a path can start and end at any node, must follow parent-child edges, and cannot revisit nodes. Ask about input size, node value ranges, and whether the tree can be empty or contain negative values.

2. Define the recursive state

For each node, define a function that returns the maximum sum of a downward path starting at that node and going into at most one child. This represents the best contribution the node can offer to its parent.

3. Compute local and global candidates

At each node, compute the best downward path through the left child and right child (clamping negative values to 0). The best path that bends at this node is node.val + leftGain + rightGain; update the global maximum with this value.

4. Return the single-branch gain

Return node.val + max(leftGain, rightGain) to the parent, since a path can only continue in one direction upward. This ensures the parent can form a valid path.

5. Analyze complexity and edge cases

State that the algorithm runs in O(n) time and O(h) space (recursion stack). Discuss edge cases: single node, all negative values, skewed trees, and empty tree.

Key Points to Mention

  • Post-order DFS (bottom-up) to compute subtree contributions
  • Global variable to track the maximum path sum seen so far
  • Clamping negative subtree sums to 0 to avoid reducing the total
  • Distinction between the value returned to the parent (single branch) and the value used to update the global max (possibly two branches)
  • Time complexity O(n) and space complexity O(h) due to recursion
  • Handling of negative values and the case where the maximum path is a single node

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.