← Meta Interview Insights

Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Meta SWE coding round, one problem, classic tree stuff. Nothing too wild but the details matter more than you'd think.

Questions Asked (1)

Q1

Given a binary tree where nodes can hold negative integers, find the maximum sum achievable along any path in the tree. The path can start and end at any nodes and doesn't need to pass through the root.

Algorithms & Data Structures
Author's notes

The key thing that trips people up is that a path can't branch, so you can't return a forked value upward.

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 updating a global maximum with the best path sum through that node (left + node + right). Handle negative values by allowing paths to start/end anywhere and considering single-node paths.

Pro tip: Explicitly discuss how you handle negative values: if a child's downward sum is negative, treat it as 0 to avoid reducing the total. Also, mention that the global maximum must be updated at every node, not just the root.

1. Clarify the problem

Confirm that a path can start and end at any nodes, may go through the root or not, and can consist of a single node. Ask if the tree can be empty or have only negative values.

2. Define the recursive function

Design a DFS that returns the maximum sum of a downward path starting at the current node (including the node itself). This path can go to at most one child.

3. Compute the best path through each node

At each node, compute the maximum path sum that passes through the node and goes into both left and right subtrees: node.val + max(0, left) + max(0, right). Update a global maximum with this value.

4. Return the downward path sum

Return node.val + max(0, left, right) to the parent, since a path cannot split at the parent. Use max(0, ...) to ignore negative contributions.

5. Analyze complexity and edge cases

State that the time complexity is O(n) and space is O(h) for recursion stack. Discuss edge cases: all negative nodes, single node, skewed tree.

Key Points to Mention

  • Post-order traversal (DFS) to process children before parent
  • Global variable to track the maximum path sum found so far
  • Handling negative values by taking max(0, child_sum) to avoid decreasing the sum
  • The difference between the value returned to the parent (single downward path) and the value used to update the global maximum (path through node with two branches)
  • Time complexity O(n) and space complexity O(h) where h is tree height
  • Edge cases: empty tree, all negative values, single node tree

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