← Adobe Interview InsightsSoftware Engineer

Adobe·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Adobe coding round, one problem, tree stuff. The question itself wasn't too bad once I figured out the pattern but getting there took longer than I'd like to admit.

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 (not necessarily the root).

Algorithms & Data Structures
Author's notes

I kept getting tripped up because I assumed the path had to go through the root.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a post-order DFS that returns the maximum gain from each subtree while updating a global maximum with the best path through the current node. At each node, compute the best downward path and consider combining the left and right gains to form a path that passes through the node.

Pro tip: Explicitly state that you ignore negative subtree contributions by taking max(0, gain) to avoid dragging down the sum, and mention that this handles edge cases like single-node trees and all-negative values.

1. Clarify the problem and constraints

Confirm that the path can start and end at any node, must follow parent-child connections, and that node values can be negative. Ask about input size to discuss recursion depth or iterative alternatives.

2. Define the recursive return value

For each node, return the maximum sum of a downward path starting at that node and extending into at most one child. This represents the best gain the node can contribute to its parent.

3. Update the global maximum

At each node, compute the best path that passes through the node by adding the node's value to the positive gains from left and right subtrees. Update a global variable with this sum.

4. Handle negative contributions

When computing gains from children, use max(0, childGain) so that negative subtrees are excluded. This ensures the path sum is maximized.

5. Analyze complexity and edge cases

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

Key Points to Mention

  • Post-order traversal (DFS) to process children before parent
  • Global variable to track the maximum path sum found so far
  • Return value is the maximum downward path sum from the current node
  • Use max(0, childGain) to ignore negative subtrees
  • Time complexity O(n) and space complexity O(h) for recursion stack
  • Edge cases: empty tree, single node, all negative values, skewed tree

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