Given a binary tree where each node contains an integer value (which can be negative), find the maximum path sum. A path is defined as any sequence of nodes connected by edges, where each node appears at most once. The path does not need to pass through the root or start/end at a leaf.
For example:
-10
/ \
9 20
/ \
15 7Maximum path sum: 42 (path: 15 -> 20 -> 7)
Another example:
-3
Maximum path sum: -3 (single node)
What makes this problem tricky compared to a simple root-to-leaf path sum? How do you handle negative values?
Explain your approach and analyze the time and space complexity.
How to approach it
- Hint 1
The maximum path can start and end at any node, not necessarily root or leaves. It can also be a single node.
- Hint 2
At each node, you have a choice: the maximum path through this node could include the left subtree, right subtree, both, or neither (just the node itself).
- Hint 3
Key distinction: when reporting to the parent, you can only include one branch (a path cannot fork). But for updating the global maximum, you can include both branches through the current node.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.