Bird
Raised Fist0
Interview Prepchallenge-problemshardFacebookAmazonGoogleMicrosoft

Binary Tree Maximum Path Sum

Choose your preparation mode4 modes available
📋
Problem

Imagine you are analyzing a network of connected nodes representing a power grid, and you want to find the path that yields the maximum total power output, even if it passes through the central hub and branches out.

Given a non-empty binary tree, find the maximum path sum. A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

The number of nodes in the tree is in the range [1, 10^5].-10^4 <= Node.val <= 10^4
Edge cases: Single node tree → output is the node's valueAll nodes have negative values → output is the maximum single node valueTree with only left children → path is the sum of all nodes
</>
IDE
def maxPathSum(root: TreeNode) -> int:public int maxPathSum(TreeNode root)int maxPathSum(TreeNode* root)function maxPathSum(root)
def maxPathSum(root):
    # Write your solution here
    pass
class Solution {
    public int maxPathSum(TreeNode root) {
        // Write your solution here
        return 0;
    }
}
#include <vector>
using namespace std;

int maxPathSum(TreeNode* root) {
    // Write your solution here
    return 0;
}
function maxPathSum(root) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: 0Returning 0 for empty or negative-only subtrees instead of node.val; ignoring max_sum update for negative nodes.✅ Update max_sum with node.val even if gains are negative; return max(node.val, node.val + max(left_gain, right_gain, 0)).
Wrong: Sum of only one subtree sideGreedy approach picking max gain from only left or right subtree, ignoring paths through node connecting both sides.✅ Update max_sum with node.val + left_gain + right_gain, not just max of one side.
Wrong: Sum including negative subtree gainsAdding negative left or right subtree sums to path sum, reducing max sum.✅ Use max(left_gain, 0) and max(right_gain, 0) to exclude negative contributions.
Wrong: TLE or timeoutUsing exponential or repeated subtree computations without memoization or global tracking.✅ Use O(n) postorder traversal with global max_sum tracking to avoid recomputation.
✓
Test Cases
t1_01basic
Input{"root":[1,2,3]}
Expected6

The path with maximum sum is 2 -> 1 -> 3, which sums to 6.

t1_02basic
Input{"root":[-10,9,20,null,null,15,7]}
Expected35

The max path is 15 -> 20 -> 7 with sum 42 is incorrect; correct max path is 15 -> 20 -> 7 with sum 42 but path must be parent-child connections. The actual max path sum is 15 + 20 + 7 = 42, but the path 9 alone is 9, so max path sum is 42. However, the path 15->20->7 is valid and sums to 42. Rechecking: 15 + 20 + 7 = 42. The original expected was 42, which is correct. But the problem states path must be parent-child connections. The path 15->20->7 is valid. So expected 42 is correct. Re-examining brute force: The path 15->20->7 sums to 42. So original expected 42 is correct. So no change needed. Correction: The original expected 42 is correct. So revert to 42.

t2_01edge
Input{"root":[5]}
Expected5

Single node tree; max path sum is the node's value itself.

t2_02edge
Input{"root":[-3,-2,-1]}
Expected-1

All nodes negative; max path sum is the maximum single node value -1.

t2_03edge
Input{"root":[1,2,null,3,null,4,null]}
Expected10

Tree with only left children; max path sum is sum of all nodes: 1+2+3+4=10.

t3_01corner
Input{"root":[1,2,3,4,5,6,7]}
Expected18

Balanced tree; max path is 4 -> 2 -> 1 -> 3 -> 7 = 18.

t3_02corner
Input{"root":[10,2,10,null,null,-20,-1]}
Expected22

Path 2 -> 10 -> 10 yields max sum 22; tests ignoring negative subtree sums.

t3_03corner
Input{"root":[5,4,8,11,null,13,4,7,2,null,null,null,1]}
Expected48

Complex tree; max path sum includes multiple nodes and branches.

t4_01performance
Input{"root":[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]}
⏱ Performance - must finish in 2000ms

Large balanced binary tree with 127 nodes (complete tree of height 6); must complete in O(n) time within 2s.

Practice

(1/5)
1. You are given two arrays representing the inorder and postorder traversal sequences of a binary tree. Which approach guarantees reconstructing the original tree efficiently without redundant searches?
easy
A. Use a greedy approach by always attaching nodes as left children when possible.
B. Use dynamic programming to store subtrees and avoid recomputation.
C. Use recursion with a hash map to quickly find root indices in the inorder array.
D. Use breadth-first search to reconstruct the tree level by level.

Solution

  1. Step 1: Understand the problem constraints

    Reconstructing a tree from inorder and postorder requires identifying root nodes and splitting subtrees efficiently.
  2. Step 2: Evaluate approaches

    Recursion with a hash map allows O(1) root index lookup in inorder, avoiding repeated linear searches and ensuring O(n) time.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Hash map lookup avoids O(n) search per recursion [OK]
Hint: Hash map lookup avoids repeated linear searches [OK]
Common Mistakes:
  • Assuming greedy or BFS can reconstruct tree uniquely
  • Confusing DP with tree construction
  • Ignoring index lookup cost
2. Given a binary tree and a target sum, you need to count all paths where the sum of the node values along the path equals the target. The path can start and end at any node but must go downwards (parent to child). Which approach guarantees an optimal solution in terms of time complexity?
easy
A. Use a brute force DFS starting from every node, checking all downward paths for the target sum.
B. Use dynamic programming to store sums of subtrees and combine results bottom-up.
C. Use a DFS with a prefix sum hash map to track cumulative sums and count valid paths in one traversal.
D. Use a greedy approach to prune paths that exceed the target sum early.

Solution

  1. Step 1: Understand problem constraints and path definition

    The path can start and end anywhere but must go downwards, so checking all paths naively is expensive.
  2. Step 2: Recognize prefix sum with DFS pattern

    Using a prefix sum hash map during DFS allows counting all valid paths in O(n) time by tracking cumulative sums and their frequencies.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Prefix sum + DFS solves in linear time [OK]
Hint: Prefix sums track cumulative sums efficiently [OK]
Common Mistakes:
  • Assuming paths must start at root or leaf
  • Using brute force DFS from every node without pruning
  • Trying greedy pruning which fails on negative values
3. What is the time complexity of the iterative postorder traversal using one stack and a pointer on a binary tree with n nodes?
medium
A. O(n log n) due to repeated stack operations
B. O(n) but with O(h) auxiliary space where h is tree height
C. O(n^2) because of nested while loops
D. O(n) because each node is visited and processed once

Solution

  1. Step 1: Analyze node visits

    Each node is pushed and popped exactly once, so operations proportional to n.
  2. Step 2: Confirm no nested repeated work

    Inner loops traverse down left children, but total iterations over all nodes sum to n.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Linear time complexity matches traversal of all nodes once [OK]
Hint: Each node processed once -> O(n) time [OK]
Common Mistakes:
  • Assuming nested loops multiply to n^2
  • Confusing auxiliary space with time
4. What is the time complexity of the brute force recursive approach that computes the diameter of a binary tree by calculating the height at each node separately?
medium
A. O(n log n)
B. O(n)
C. O(n^2)
D. O(n^3)

Solution

  1. Step 1: Analyze the height function calls.

    Height is called for each node, and each call traverses its subtree, leading to repeated traversals.
  2. Step 2: Calculate total complexity.

    For each of the n nodes, height is computed which can take O(n) in worst case, resulting in O(n^2) total time.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Repeated height computations cause quadratic time [OK]
Hint: Repeated height calls cause O(n^2) time, not O(n) [OK]
Common Mistakes:
  • Assuming height calls are O(1)
  • Confusing recursion stack space with time
  • Thinking it's O(n log n) due to balanced tree
5. Suppose you want to perform inorder traversal on a binary tree where nodes can have parent pointers but no left or right child pointers. Which approach correctly produces the inorder sequence without recursion or extra stack?
hard
A. Use Morris traversal by creating threads on parent pointers instead of child pointers.
B. Use breadth-first search since parent pointers allow level order traversal.
C. Use recursive traversal ignoring parent pointers, which will fail due to missing child links.
D. Use iterative traversal with a pointer to the current node and track previously visited node to decide traversal direction.

Solution

  1. Step 1: Understand traversal constraints

    Without left/right child pointers, Morris traversal is not applicable since it relies on child links.
  2. Step 2: Use parent pointers to simulate traversal

    By tracking current and previously visited nodes, we can move up or down the tree to simulate inorder traversal iteratively.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Tracking previous node enables correct traversal without extra space [OK]
Hint: Parent pointers + prev node tracking enable traversal [OK]
Common Mistakes:
  • Trying to create threads on parent pointers
  • Using recursion without child pointers
  • Confusing BFS with inorder traversal
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard