Binary Tree Maximum Path Sum

🎯

Binary Tree Maximum Path Sum

hardMIXEDFacebookAmazonGoogle

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.

💡 This problem involves finding the maximum sum path in a binary tree, which is challenging because the path can start and end at any node, not necessarily the root or leaves. Beginners often struggle to understand how to consider paths that bend at a node and how to efficiently compute the maximum sum without redundant calculations.

📋

Problem Statement

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

💡

Example

Input"[1,2,3]"

Output6

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

Input"[-10,9,20,null,null,15,7]"

Output42

The path with maximum sum is 15 -> 20 -> 7, which sums to 42.

• Single node tree → output is the node's value
• All nodes have negative values → output is the maximum single node value
• Tree with only left children → path is the sum of all nodes
• Tree with only right children → path is the sum of all nodes

⚠️

Common Mistakes

Not ignoring negative gains from subtrees

Path sum decreases incorrectly, leading to wrong max sum

✅ Use max(child_gain, 0) to ignore negative contributions

Returning sum of both children to parent

Incorrect path sums and double counting, causing wrong results

✅ Return node value plus max of left or right gain only

Not updating global max path sum at each node

Misses paths that bend at current node, leading to suboptimal answer

✅ Update global max with node.val + left_gain + right_gain at each node

Using recursion without base case for null nodes

Runtime errors or infinite recursion

✅ Return 0 for null nodes in recursion

Assuming path must start at root or leaf

Incorrect max path sum calculation

✅ Allow path to start and end at any node

🧠

Brute Force (Pure Recursion / Nested Loops / etc.)

💡 Starting with brute force helps understand the problem's complexity by trying all possible paths, even though it's inefficient. It lays the foundation for more optimized solutions.

Intuition

Try every possible path in the tree by exploring all nodes and all paths starting from each node, then find the maximum sum among them.

Algorithm

1. Define a helper function to compute the maximum path sum starting from a given node.
2. For each node in the tree, compute the maximum path sum that passes through it by exploring all possible paths.
3. Keep track of the global maximum path sum found so far.
4. Return the global maximum after exploring all nodes.

💡 This approach is hard because it redundantly computes path sums multiple times and doesn't reuse results, leading to exponential time.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root):
    max_sum = float('-inf')

    def max_gain(node):
        nonlocal max_sum
        if not node:
            return 0
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)
        price_newpath = node.val + left_gain + right_gain
        max_sum = max(max_sum, price_newpath)
        return node.val + max(left_gain, right_gain)

    max_gain(root)
    return max_sum

# Driver code
if __name__ == '__main__':
    root = TreeNode(-10)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(maxPathSum(root))  # Output: 42

Line Notes

def maxPathSum(root):Defines the main function to compute max path sum

max_sum = float('-inf')Initialize global max to smallest possible to handle negative values

def max_gain(node):Helper function to compute max gain from current node

if not node:Base case: null nodes contribute 0 to path sum

left_gain = max(max_gain(node.left), 0)Ignore negative gains from left subtree

right_gain = max(max_gain(node.right), 0)Ignore negative gains from right subtree

price_newpath = node.val + left_gain + right_gainSum if path passes through current node including both children

max_sum = max(max_sum, price_newpath)Update global max if current path is better

return node.val + max(left_gain, right_gain)Return max gain to parent, only one side can be extended

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode node) {
        if (node == null) return 0;
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);
        int priceNewPath = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, priceNewPath);
        return node.val + Math.max(leftGain, rightGain);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(-10);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        Solution sol = new Solution();
        System.out.println(sol.maxPathSum(root)); // Output: 42
    }
}

Line Notes

private int maxSum = Integer.MIN_VALUE;Initialize global max to smallest integer to handle negatives

public int maxPathSum(TreeNode root) {Main function to start recursion

if (node == null) return 0;Base case: null nodes contribute zero

int leftGain = Math.max(maxGain(node.left), 0);Ignore negative left subtree sums

int rightGain = Math.max(maxGain(node.right), 0);Ignore negative right subtree sums

int priceNewPath = node.val + leftGain + rightGain;Sum if path passes through current node

maxSum = Math.max(maxSum, priceNewPath);Update global max if better path found

return node.val + Math.max(leftGain, rightGain);Return max gain to parent, only one side extended

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
    int maxSum = INT_MIN;
public:
    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return maxSum;
    }
private:
    int maxGain(TreeNode* node) {
        if (!node) return 0;
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);
        int priceNewPath = node->val + leftGain + rightGain;
        maxSum = max(maxSum, priceNewPath);
        return node->val + max(leftGain, rightGain);
    }
};

int main() {
    TreeNode* root = new TreeNode(-10);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    Solution sol;
    cout << sol.maxPathSum(root) << endl; // Output: 42
    return 0;
}

Line Notes

int maxSum = INT_MIN;Initialize global max to smallest int to handle negative values

int maxPathSum(TreeNode* root) {Main function to start recursion

if (!node) return 0;Base case: null nodes contribute zero

int leftGain = max(maxGain(node->left), 0);Ignore negative left subtree sums

int rightGain = max(maxGain(node->right), 0);Ignore negative right subtree sums

int priceNewPath = node->val + leftGain + rightGain;Sum if path passes through current node

maxSum = max(maxSum, priceNewPath);Update global max if better path found

return node->val + max(leftGain, rightGain);Return max gain to parent, only one side extended

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function maxPathSum(root) {
    let maxSum = -Infinity;

    function maxGain(node) {
        if (!node) return 0;
        let leftGain = Math.max(maxGain(node.left), 0);
        let rightGain = Math.max(maxGain(node.right), 0);
        let priceNewPath = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, priceNewPath);
        return node.val + Math.max(leftGain, rightGain);
    }

    maxGain(root);
    return maxSum;
}

// Driver code
const root = new TreeNode(-10,
    new TreeNode(9),
    new TreeNode(20, new TreeNode(15), new TreeNode(7))
);
console.log(maxPathSum(root)); // Output: 42

Line Notes

let maxSum = -Infinity;Initialize global max to smallest number to handle negatives

function maxGain(node) {Helper function to compute max gain from current node

if (!node) return 0;Base case: null nodes contribute zero

let leftGain = Math.max(maxGain(node.left), 0);Ignore negative left subtree sums

let rightGain = Math.max(maxGain(node.right), 0);Ignore negative right subtree sums

let priceNewPath = node.val + leftGain + rightGain;Sum if path passes through current node

maxSum = Math.max(maxSum, priceNewPath);Update global max if better path found

return node.val + Math.max(leftGain, rightGain);Return max gain to parent, only one side extended

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node is visited once in postorder traversal; recursion stack uses space proportional to tree height h.

💡 For n=100,000 nodes and balanced tree height ~17, this means about 100,000 operations and stack depth 17, which is efficient.

Interview Verdict: Accepted

Though this looks like brute force, this recursive approach is actually optimal for this problem and accepted in interviews.

🧠

Iterative Postorder Traversal with Stack

💡 This approach replaces recursion with an explicit stack to avoid recursion overhead and stack overflow in very deep trees, which is important in production environments.

Intuition

Use an iterative postorder traversal to compute max gains bottom-up, simulating recursion with a stack and tracking visited nodes.

Algorithm

1. Use a stack to traverse the tree in postorder iteratively.
2. Track nodes and whether their children have been processed.
3. For each node, compute max gains from left and right children once processed.
4. Update global max path sum and store max gain for parent computations.

💡 This approach is harder to implement but avoids recursion limits and clarifies the traversal order.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root):
    if not root:
        return 0
    max_sum = float('-inf')
    stack = []
    node = root
    last_visited = None
    gains = {}

    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            peek = stack[-1]
            if peek.right and last_visited != peek.right:
                node = peek.right
            else:
                left_gain = max(gains.get(peek.left, 0), 0)
                right_gain = max(gains.get(peek.right, 0), 0)
                price_newpath = peek.val + left_gain + right_gain
                max_sum = max(max_sum, price_newpath)
                gains[peek] = peek.val + max(left_gain, right_gain)
                last_visited = stack.pop()
                node = None
    return max_sum

# Driver code
if __name__ == '__main__':
    root = TreeNode(-10)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(maxPathSum(root))  # Output: 42

Line Notes

stack = []Initialize stack to simulate recursion

while stack or node:Loop until all nodes processed

if node:Go as left as possible

if peek.right and last_visited != peek.right:Process right child if not visited

left_gain = max(gains.get(peek.left, 0), 0)Get left child's max gain or 0 if none

right_gain = max(gains.get(peek.right, 0), 0)Get right child's max gain or 0 if none

max_sum = max(max_sum, price_newpath)Update global max path sum

gains[peek] = peek.val + max(left_gain, right_gain)Store max gain for parent use

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        int maxSum = Integer.MIN_VALUE;
        Map<TreeNode, Integer> gains = new HashMap<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root, lastVisited = null;

        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right != null && lastVisited != peek.right) {
                    node = peek.right;
                } else {
                    int leftGain = Math.max(gains.getOrDefault(peek.left, 0), 0);
                    int rightGain = Math.max(gains.getOrDefault(peek.right, 0), 0);
                    int priceNewPath = peek.val + leftGain + rightGain;
                    maxSum = Math.max(maxSum, priceNewPath);
                    gains.put(peek, peek.val + Math.max(leftGain, rightGain));
                    lastVisited = stack.pop();
                    node = null;
                }
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(-10);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        Solution sol = new Solution();
        System.out.println(sol.maxPathSum(root)); // Output: 42
    }
}

Line Notes

Map<TreeNode, Integer> gains = new HashMap<>();Store max gains for nodes to avoid recomputation

Deque<TreeNode> stack = new ArrayDeque<>();Stack to simulate recursion

while (!stack.isEmpty() || node != null) {Traverse until all nodes processed

if (peek.right != null && lastVisited != peek.right) {Process right child if not visited

int leftGain = Math.max(gains.getOrDefault(peek.left, 0), 0);Get left child's max gain or 0

int rightGain = Math.max(gains.getOrDefault(peek.right, 0), 0);Get right child's max gain or 0

maxSum = Math.max(maxSum, priceNewPath);Update global max path sum

gains.put(peek, peek.val + Math.max(leftGain, rightGain));Store max gain for parent use

#include <iostream>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <climits>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        if (!root) return 0;
        int maxSum = INT_MIN;
        stack<TreeNode*> stk;
        unordered_map<TreeNode*, int> gains;
        TreeNode* node = root;
        TreeNode* lastVisited = nullptr;

        while (!stk.empty() || node) {
            if (node) {
                stk.push(node);
                node = node->left;
            } else {
                TreeNode* peek = stk.top();
                if (peek->right && lastVisited != peek->right) {
                    node = peek->right;
                } else {
                    int leftGain = max(gains[peek->left], 0);
                    int rightGain = max(gains[peek->right], 0);
                    int priceNewPath = peek->val + leftGain + rightGain;
                    maxSum = max(maxSum, priceNewPath);
                    gains[peek] = peek->val + max(leftGain, rightGain);
                    lastVisited = peek;
                    stk.pop();
                    node = nullptr;
                }
            }
        }
        return maxSum;
    }
};

int main() {
    TreeNode* root = new TreeNode(-10);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    Solution sol;
    cout << sol.maxPathSum(root) << endl; // Output: 42
    return 0;
}

Line Notes

stack<TreeNode*> stk;Stack to simulate recursion

unordered_map<TreeNode*, int> gains;Map to store max gains for nodes

while (!stk.empty() || node) {Traverse until all nodes processed

if (peek->right && lastVisited != peek->right) {Process right child if not visited

int leftGain = max(gains[peek->left], 0);Get left child's max gain or 0

int rightGain = max(gains[peek->right], 0);Get right child's max gain or 0

maxSum = max(maxSum, priceNewPath);Update global max path sum

gains[peek] = peek->val + max(leftGain, rightGain);Store max gain for parent use

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function maxPathSum(root) {
    if (!root) return 0;
    let maxSum = -Infinity;
    const stack = [];
    const gains = new Map();
    let node = root;
    let lastVisited = null;

    while (stack.length > 0 || node !== null) {
        if (node !== null) {
            stack.push(node);
            node = node.left;
        } else {
            const peek = stack[stack.length - 1];
            if (peek.right !== null && lastVisited !== peek.right) {
                node = peek.right;
            } else {
                const leftGain = Math.max(gains.get(peek.left) || 0, 0);
                const rightGain = Math.max(gains.get(peek.right) || 0, 0);
                const priceNewPath = peek.val + leftGain + rightGain;
                maxSum = Math.max(maxSum, priceNewPath);
                gains.set(peek, peek.val + Math.max(leftGain, rightGain));
                lastVisited = stack.pop();
                node = null;
            }
        }
    }
    return maxSum;
}

// Driver code
const root = new TreeNode(-10,
    new TreeNode(9),
    new TreeNode(20, new TreeNode(15), new TreeNode(7))
);
console.log(maxPathSum(root)); // Output: 42

Line Notes

const stack = [];Stack to simulate recursion

const gains = new Map();Map to store max gains for nodes

while (stack.length > 0 || node !== null) {Traverse until all nodes processed

if (peek.right !== null && lastVisited !== peek.right) {Process right child if not visited

const leftGain = Math.max(gains.get(peek.left) || 0, 0);Get left child's max gain or 0

const rightGain = Math.max(gains.get(peek.right) || 0, 0);Get right child's max gain or 0

maxSum = Math.max(maxSum, priceNewPath);Update global max path sum

gains.set(peek, peek.val + Math.max(leftGain, rightGain));Store max gain for parent use

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once; stack and map use O(n) space in worst case for skewed trees.

💡 For large trees, this approach avoids recursion stack overflow but uses extra memory for the stack and map.

Interview Verdict: Accepted

This approach is practical for very deep trees where recursion might fail, though more complex to implement.

🧠

Optimized Recursive Approach with Global Tracking

💡 This is the standard optimal solution that uses recursion with a global variable to track the maximum path sum, combining clarity and efficiency.

Intuition

Use postorder traversal to compute max gain from each node, updating a global max path sum that considers paths passing through the node including both children.

Algorithm

1. Define a recursive helper function that returns the max gain from a node to its parent.
2. At each node, compute max gains from left and right children, ignoring negative gains.
3. Calculate the price of a new path passing through the node (node value + left gain + right gain).
4. Update the global maximum path sum if the new path is better.
5. Return the max gain to the parent (node value + max of left or right gain).

💡 This approach is elegant because it combines the exploration and global update in one traversal without extra data structures.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root):
    max_sum = float('-inf')

    def helper(node):
        nonlocal max_sum
        if not node:
            return 0
        left = max(helper(node.left), 0)
        right = max(helper(node.right), 0)
        max_sum = max(max_sum, node.val + left + right)
        return node.val + max(left, right)

    helper(root)
    return max_sum

# Driver code
if __name__ == '__main__':
    root = TreeNode(-10)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(maxPathSum(root))  # Output: 42

Line Notes

max_sum = float('-inf')Initialize global max to smallest number to handle negatives

def helper(node):Recursive helper to compute max gain from node

if not node:Base case: null nodes contribute zero

left = max(helper(node.left), 0)Ignore negative left subtree sums

right = max(helper(node.right), 0)Ignore negative right subtree sums

max_sum = max(max_sum, node.val + left + right)Update global max path sum including both children

return node.val + max(left, right)Return max gain to parent, only one side extended

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        helper(root);
        return maxSum;
    }

    private int helper(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(helper(node.left), 0);
        int right = Math.max(helper(node.right), 0);
        maxSum = Math.max(maxSum, node.val + left + right);
        return node.val + Math.max(left, right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(-10);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        Solution sol = new Solution();
        System.out.println(sol.maxPathSum(root)); // Output: 42
    }
}

Line Notes

private int maxSum = Integer.MIN_VALUE;Initialize global max to smallest integer to handle negatives

public int maxPathSum(TreeNode root) {Main function to start recursion

if (node == null) return 0;Base case: null nodes contribute zero

int left = Math.max(helper(node.left), 0);Ignore negative left subtree sums

int right = Math.max(helper(node.right), 0);Ignore negative right subtree sums

maxSum = Math.max(maxSum, node.val + left + right);Update global max path sum including both children

return node.val + Math.max(left, right);Return max gain to parent, only one side extended

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
    int maxSum = INT_MIN;
public:
    int maxPathSum(TreeNode* root) {
        helper(root);
        return maxSum;
    }
private:
    int helper(TreeNode* node) {
        if (!node) return 0;
        int left = max(helper(node->left), 0);
        int right = max(helper(node->right), 0);
        maxSum = max(maxSum, node->val + left + right);
        return node->val + max(left, right);
    }
};

int main() {
    TreeNode* root = new TreeNode(-10);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    Solution sol;
    cout << sol.maxPathSum(root) << endl; // Output: 42
    return 0;
}

Line Notes

int maxSum = INT_MIN;Initialize global max to smallest int to handle negative values

int maxPathSum(TreeNode* root) {Main function to start recursion

if (!node) return 0;Base case: null nodes contribute zero

int left = max(helper(node->left), 0);Ignore negative left subtree sums

int right = max(helper(node->right), 0);Ignore negative right subtree sums

maxSum = max(maxSum, node->val + left + right);Update global max path sum including both children

return node->val + max(left, right);Return max gain to parent, only one side extended

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function maxPathSum(root) {
    let maxSum = -Infinity;

    function helper(node) {
        if (!node) return 0;
        let left = Math.max(helper(node.left), 0);
        let right = Math.max(helper(node.right), 0);
        maxSum = Math.max(maxSum, node.val + left + right);
        return node.val + Math.max(left, right);
    }

    helper(root);
    return maxSum;
}

// Driver code
const root = new TreeNode(-10,
    new TreeNode(9),
    new TreeNode(20, new TreeNode(15), new TreeNode(7))
);
console.log(maxPathSum(root)); // Output: 42

Line Notes

let maxSum = -Infinity;Initialize global max to smallest number to handle negatives

function helper(node) {Recursive helper to compute max gain from node

if (!node) return 0;Base case: null nodes contribute zero

let left = Math.max(helper(node.left), 0);Ignore negative left subtree sums

let right = Math.max(helper(node.right), 0);Ignore negative right subtree sums

maxSum = Math.max(maxSum, node.val + left + right);Update global max path sum including both children

return node.val + Math.max(left, right);Return max gain to parent, only one side extended

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node visited once; recursion stack uses space proportional to tree height h.

💡 For n=100,000 nodes and balanced tree height ~17, this means about 100,000 operations and stack depth 17, which is efficient.

Interview Verdict: Accepted

This is the preferred approach in interviews due to its clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal recursive approach is the best choice for interviews due to its clarity and efficiency. Iterative approach is useful for very deep trees. Brute force is mainly for understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive with global tracking)	O(n)	O(h)	Yes (deep recursion)	No (only sum returned)	Code this approach; it is optimal and accepted
2. Iterative Postorder Traversal	O(n)	O(n)	No	No	Mention if recursion depth is a concern
3. Naive Brute Force (Try all paths)	O(n^2) or worse	O(h)	Yes	No	Mention only to explain problem complexity

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding, and finally implement the optimal solution. Practice coding and testing edge cases.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to demonstrate understanding.Step 3: Explain why brute force is inefficient and introduce the optimized recursive solution.Step 4: Write clean, well-commented code for the optimal approach.Step 5: Test your code with provided and edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of tree traversal, handling negative values, and ability to optimize recursion with global tracking. They also assess your coding clarity and testing thoroughness.

Common Follow-ups

• How would you handle very deep trees to avoid stack overflow? → Use iterative traversal or tail recursion optimization.
• Can you modify the solution to return the actual path, not just the sum? → Track nodes along with sums during recursion.

💡 These follow-ups test your ability to adapt solutions for practical constraints and extend functionality.

🔍

Pattern Recognition

When to Use

1) Problem involves binary tree paths, 2) Path can start and end anywhere, 3) Need max sum or max value, 4) Negative values present

Signature Phrases

maximum path sumpath can start and end at any nodebinary tree

NOT This Pattern When

Longest root-to-leaf path sum problems, which restrict paths to root-leaf only

Similar Problems

Binary Tree Diameter - similar tree traversal and path conceptsPath Sum III - related to path sums but with different constraints

Practice

1. Consider the following Python code implementing the optimized LIS algorithm. What is the value of the variable tails after processing the input [3, 1, 2]?

easy

A. [1, 2, 3]

B. [1, 2]

C. [1, 3]

D. [3, 1, 2]

Solution

1. Step 1: Process num=3

   tails is empty, bisect_left returns 0, append 3 -> tails = [3]

2. Step 2: Process num=1

   bisect_left(tails,1) returns 0, replace tails[0] with 1 -> tails = [1]

3. Step 3: Process num=2

   bisect_left(tails,2) returns 1 (end of tails), append 2 -> tails = [1, 2]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   tails always sorted and minimal last elements [OK]

Hint: tails stores smallest possible ends of subsequences [OK]

Common Mistakes:

• Appending instead of replacing in tails
• Misunderstanding bisect_left index
• Confusing tails with actual subsequence

2. Consider the following code snippet implementing the bottom-up bitmask DP for shortest path visiting all nodes. Given the input graph [[1,2,3],[0],[0],[0]], what is the final returned value?

easy

A. 4

B. 3

C. 5

D. 6

Solution

1. Step 1: Initialize dp for each node with mask of only that node visited

   dp[i][1 << i] = 0 for i in [0..3].

2. Step 2: Iterate over all masks and update dp for neighbors

   For mask=1 (node 0 visited), neighbors 1,2,3 get dp updated to 1. Then masks with multiple nodes visited get updated with shortest distances. The minimal path visiting all nodes is length 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches example usage print statement [OK]

Hint: Final answer matches minimal steps to cover all nodes [OK]

Common Mistakes:

• Off-by-one in dp updates
• Confusing mask updates
• Misreading graph edges

3. What is the time complexity of the space optimized bitmask DP solution for counting ways to assign unique caps to n people, where caps range up to 100 and each person has a list of caps they can wear?

medium

A. O(n * 2^n)

B. O(100 * 2^n * n)

C. O(2^n * n^2)

D. O(n * 100^n)

Solution

1. Step 1: Identify loops in the algorithm

   The outer loop iterates over caps (up to 100), the middle loop iterates over all masks (2^n), and the inner loop iterates over persons (up to n) who can wear the current cap.

2. Step 2: Combine loop complexities

   Multiplying these gives O(100 * 2^n * n). Other options either omit the cap factor or incorrectly exponentiate caps.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Counting all masks and caps with person checks matches O(100 * 2^n * n) [OK]

Hint: Count loops: caps * masks * persons per cap [OK]

Common Mistakes:

• Ignoring caps loop
• Confusing n with cap count
• Forgetting inner loop over persons

4. What is the time complexity of the topological sort based DP solution for the longest increasing path in an m x n matrix?

medium

A. O(m * n * log(m * n))

B. O(m * n^2)

C. O(m * n * 4^{m*n})

D. O(m * n)

Solution

1. Step 1: Identify sorting cost

   Sorting all m*n cells by their values costs O(m*n*log(m*n)).

2. Step 2: Analyze DP updates

   Each cell checks up to 4 neighbors, so DP updates cost O(m*n) total.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates, so complexity is O(m*n*log(m*n)) [OK]

Hint: Sorting cells dominates complexity [OK]

Common Mistakes:

• Assuming DP is O(m*n) ignoring sorting
• Confusing exponential brute force with DP
• Ignoring log factor from sorting

5. Suppose the House Robber III problem is modified so that you can rob the same node multiple times (i.e., unlimited reuse), but still cannot rob directly connected nodes in the same iteration. Which of the following changes to the algorithm is correct to handle this variant efficiently?

hard

A. Modify DP states to track how many times each node is robbed and use memoization accordingly

B. Use the same DP but multiply node values by the number of times robbed, no other changes needed

C. The problem reduces to a maximum weighted independent set on a tree with unlimited reuse, which is NP-hard, so no efficient solution exists

D. Transform the tree into a graph and run a maximum weighted matching algorithm

Solution

1. Step 1: Understand problem change

   Allowing multiple robberies per node requires tracking counts per node, not just binary rob/not_rob states.

2. Step 2: Adapt DP states

   DP must be extended to track how many times a node is robbed and ensure adjacency constraints per iteration, requiring more complex memoization.

3. Step 3: Reject incorrect options

   Simply multiplying values ignores adjacency constraints; problem remains polynomial on trees, so NP-hard claim is false; maximum weighted matching is unrelated.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Extended DP with counts handles reuse and adjacency constraints [OK]

Hint: Reusing nodes requires richer DP states, not just value scaling [OK]

Common Mistakes:

• Assuming problem becomes NP-hard or unchanged