Bird
Raised Fist0
Interview Prepchallenge-problemshardFacebookAmazonGoogleMicrosoft

Binary Tree Maximum Path Sum

Choose your preparation mode4 modes available
🎯
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.
ApproachTimeSpaceStack RiskReconstructUse 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 TraversalO(n)O(n)NoNoMention if recursion depth is a concern
3. Naive Brute Force (Try all paths)O(n^2) or worseO(h)YesNoMention 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/5)
1. What is the time complexity of the optimal greedy postorder traversal solution for the Binary Tree Cameras problem, and why?
medium
A. O(n) because each node is visited once in postorder traversal
B. O(n^2) because each node's state depends on its children's states recursively
C. O(n log n) due to recursive calls and state checks at each node
D. O(h) where h is the height of the tree, since recursion depth equals height

Solution

  1. Step 1: Analyze traversal visits

    The algorithm visits each node exactly once in a postorder manner, processing left and right children before the node itself.
  2. Step 2: Consider work per node

    Each node's processing is O(1) -- checking children's states and updating counters.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Single DFS traversal over n nodes -> O(n) time [OK]
Hint: Each node processed once with constant work [OK]
Common Mistakes:
  • Assuming recursive calls multiply work to O(n^2)
  • Confusing recursion depth with total work
  • Thinking state checks add log n factor
2. Consider this modified Morris inorder traversal code snippet. Which line contains a subtle bug that can cause infinite loops or incorrect output on some trees?
def inorderTraversal(root):
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current  # create thread
                current = current.left
            else:
                # BUG: missing line to remove thread
                result.append(current.val)
                current = current.right
    return result
medium
A. Missing line resetting predecessor.right = None to remove thread
B. Line moving current to current.left after creating thread
C. Line appending current.val after detecting thread
D. Line setting predecessor.right = current (creating thread)

Solution

  1. Step 1: Identify thread removal step

    Morris traversal requires removing the temporary thread by setting predecessor.right = None after visiting the node.
  2. Step 2: Locate missing removal

    The code lacks the line resetting predecessor.right = None, causing infinite loops or corrupted tree structure.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Without removing thread, traversal loops endlessly [OK]
Hint: Always remove threads to restore tree [OK]
Common Mistakes:
  • Forgetting to remove thread
  • Appending node before removing thread
  • Incorrectly creating thread
3. The following BFS-based code attempts to compute the maximum depth of a binary tree. Identify the line containing the subtle bug that causes incorrect depth calculation for an empty tree input.
from collections import deque

def maxDepth(root):
    queue = deque([root])
    depth = 0
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1
    return depth
medium
A. Line 7: Using len(queue) to determine level size
B. Line 15: Incrementing depth after processing each level
C. Line 10: Popping node from queue without null check
D. Line 2: Initializing queue with root without checking if root is null

Solution

  1. Step 1: Check handling of empty tree

    Code initializes queue with root without checking if root is null, so if root is null, queue contains null, causing errors.
  2. Step 2: Verify other lines

    len(queue) and popping nodes are correct if queue is valid; depth increment is necessary after each level.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Missing root null check causes failure on empty tree [OK]
Hint: Always check for null root before queue initialization [OK]
Common Mistakes:
  • Not handling empty tree input
  • Assuming root always exists
  • Incrementing depth incorrectly
4. Consider the following buggy deserialization code snippet for BFS-based tree reconstruction. Which line contains the subtle bug that causes incorrect tree structure when deserializing?
def deserialize(data):
    if not data:
        return None
    vals = data.split(',')
    root = TreeNode(int(vals[0]))
    queue = deque([root])
    i = 1
    while queue:
        node = queue.popleft()
        if vals[i] != 'X':
            node.left = TreeNode(int(vals[i]))
            queue.append(node.left)
        i += 1
        if vals[i] != 'X':
            node.right = TreeNode(int(vals[i]))
            queue.append(node.right)
        i += 1
    return root
medium
A. Line: if vals[i] != 'X': (left child check)
B. Line: i += 1 (after left child assignment)
C. Line: if vals[i] != 'X': (right child check)
D. Line: while queue: (loop condition)

Solution

  1. Step 1: Identify potential infinite loop

    The loop condition 'while queue:' does not check if 'i' has exceeded vals length, risking index out of range or infinite loop.
  2. Step 2: Understand impact on deserialization

    Without checking 'i < len(vals)', the loop may continue after all nodes processed, causing errors or incorrect tree structure.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Loop condition must ensure 'i' stays within bounds to avoid deserialization bugs [OK]
Hint: Loop must check index bounds to avoid infinite loops [OK]
Common Mistakes:
  • Not checking index bounds in deserialization loops
  • Mixing up left and right child assignments
  • Forgetting to append children to queue
5. If the problem is modified so that the postorder traversal may contain duplicate values, which of the following changes is necessary to correctly reconstruct the tree?
hard
A. Modify the algorithm to store indices of all occurrences of each value in inorder and track usage to avoid ambiguity.
B. Use a hash map from value to index in inorder traversal as before, ignoring duplicates.
C. Switch to preorder and inorder traversals which do not have duplicates.
D. Use a greedy approach attaching nodes as left children to handle duplicates.

Solution

  1. Step 1: Understand the impact of duplicates

    Duplicates break the uniqueness of value-to-index mapping in inorder traversal, so a simple hash map is insufficient.
  2. Step 2: Required modification

    Store all indices of each value in inorder and track which occurrence is used to correctly split subtrees and avoid ambiguity.
  3. Step 3: Why other options fail

    Ignoring duplicates or switching traversals does not solve ambiguity; greedy approach fails to reconstruct correct structure.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Tracking multiple indices per value is necessary for duplicates [OK]
Hint: Duplicates require tracking all indices, not just one [OK]
Common Mistakes:
  • Ignoring duplicates in hash map
  • Assuming unique values always
  • Switching traversal types incorrectly
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