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. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the edit distance problem, where the input strings have lengths m and n respectively?

medium

A. O(m * n)

B. O(m + n)

C. O(m * n * min(m, n))

D. O(3^(m + n))

Solution

1. Step 1: Identify nested loops over m and n

   The algorithm iterates over all pairs of indices (i, j) with i in [0, m) and j in [0, n), performing constant work per pair.

2. Step 2: Confirm no extra multiplicative factors

   Each cell computation is O(1), so total time is O(m * n). The recursion stack or auxiliary space does not affect time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP table size m*n and constant work per cell [OK]

Hint: DP over m*n cells -> O(m*n) time [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming exponential due to recursion without memoization

2. What is the time complexity of the single pass stack-based solution for the Largest Rectangle in Histogram problem, and why might a candidate mistakenly think it is higher?

medium

A. O(n) because each bar is pushed and popped at most once

B. O(n log n) due to sorting or binary search steps

C. O(n^2) because each bar can be pushed and popped multiple times

D. O(n) but with O(n^2) auxiliary space due to recursion stack

Solution

1. Step 1: Analyze push/pop operations

   Each bar index is pushed onto the stack once and popped once when a smaller height is encountered, so total stack operations are O(n).

2. Step 2: Understand why complexity is linear

   Since the inner while loop pops bars only when a smaller height is found, total pops across all iterations sum to at most n, making the overall time O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Push/pop per bar once -> linear time [OK]

Hint: Each bar pushed and popped once -> O(n) time [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing stack operations as repeated for each iteration
• Thinking recursion or sorting is involved

3. Consider the following buggy code snippet for merging two skylines. Which line contains the subtle bug that can cause incorrect skyline output by adding redundant points or missing height changes?

medium

A. Line where maxH is computed with max(h1, h2)

B. Line where merged appends [x, maxH] without checking last height

C. Line where i and j are incremented in the else block

D. Line where h1 and h2 are initialized to 0 at the start

Solution

1. Step 1: Identify the bug

   The code appends every point without checking if the height changed, causing redundant points.

2. Step 2: Correct approach

   Appending should happen only if merged is empty or last height differs from maxH to avoid duplicates.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending unconditionally causes redundant points [OK]

Hint: Check if last height differs before appending new point [OK]

Common Mistakes:

• Appending points even if height unchanged
• Incorrectly incrementing indices causing skips
• Not initializing heights properly

4. Suppose the Alien Dictionary problem is extended so that words can be repeated multiple times in the input list, possibly introducing duplicate edges. Which modification to the optimal Kahn's algorithm approach correctly handles this scenario without corrupting the in-degree counts?

hard

A. Use a set to track edges and only add an edge and increment in-degree if it is not already present

B. Reset in-degree counts after building the graph to avoid duplicates

C. Remove the edge deduplication check and increment in-degree for every edge found

D. Use DFS instead of BFS to avoid counting duplicate edges

Solution

1. Step 1: Identify problem with duplicate edges

   Repeated words can cause multiple identical edges, inflating in-degree counts incorrectly.

2. Step 2: Use edge deduplication to prevent multiple increments

   Track edges in a set and only add/increment if edge is new, preserving correct in-degree.

3. Step 3: Confirm BFS with correct in-degree works properly

   Maintains accurate topological order and cycle detection despite duplicates.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Edge deduplication is essential for correctness with repeated words [OK]

Hint: Avoid incrementing in-degree multiple times for same edge [OK]

Common Mistakes:

• Ignoring duplicates
• Resetting in-degree incorrectly
• Switching to DFS unnecessarily

5. Suppose the problem is modified so that nodes can be revisited multiple times without penalty, but the goal remains to visit all nodes at least once with the shortest path length. Which modification to the bidirectional BFS with state compression algorithm is necessary to handle this variant correctly?

hard

A. Remove the visited bitmask and track only the current node in BFS states

B. Modify the bitmask to track the count of visits per node instead of a binary visited flag

C. Use a simple BFS without bitmask since revisits are allowed and shortest path is trivial

D. Keep the visited bitmask but allow revisiting states with the same mask and node multiple times

Solution

1. Step 1: Understand problem change

   Allowing multiple revisits without penalty means the visited state must track how many times each node is visited if that affects path validity.

2. Step 2: Modify state representation

   Binary bitmask is insufficient; need to track counts per node, e.g., using a vector or multi-bit encoding per node, to correctly represent states and avoid incorrect pruning.

3. Step 3: Implication on BFS

   State space grows, but correctness requires this richer state representation to find shortest path under new rules.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Counting visits per node is necessary when revisits are allowed without penalty [OK]

Hint: Bitmask alone can't track multiple visits; need counts per node [OK]

Common Mistakes:

• Removing bitmask entirely loses track of visited nodes
• Allowing revisits without state changes causes incorrect pruning
• Assuming simple BFS suffices without state tracking