Maximum Path Sum in Binary Tree in DSA C++ - Build from Scratch

Maximum Path Sum in Binary Tree

📖 Scenario: You are working on a program that analyzes a binary tree representing a network of connected nodes. Each node has a value that can be positive or negative. Your task is to find the maximum sum of values along any path in the tree. A path can start and end at any node, but it must follow parent-child connections.

🎯 Goal: Build a C++ program that creates a binary tree, sets up a helper variable, implements a function to find the maximum path sum, and prints the result.

📋 What You'll Learn

Create a binary tree with the exact structure and node values given

Add a helper variable to track the maximum path sum

Implement a recursive function to calculate the maximum path sum

Print the maximum path sum found in the tree

💡 Why This Matters

🌍 Real World

Finding maximum path sums in trees is useful in network analysis, game development, and decision-making systems where you want to find the best route or highest scoring path.

💼 Career

Understanding tree traversal and recursion is essential for software engineers working with hierarchical data, algorithms, and optimization problems.

1

Create the Binary Tree Structure

Create a struct called TreeNode with an int val, and two pointers left and right to TreeNode. Then create the exact binary tree below by creating TreeNode objects named root, node1, node2, node3, node4, and node5. Set their val as 1, 2, 3, 4, 5, and 6 respectively. Connect the nodes to form this tree:

1
/ \
2 3
/ \ \
4 5 6

DSA C++

// Define TreeNode struct and create nodes with values 1 to 6
// Connect nodes to form the tree
// Your code here

Hint

Define the TreeNode struct first. Then create each node with the exact values. Finally, connect the nodes to form the tree as shown.

2

Add a Helper Variable for Maximum Path Sum

Add a global variable called maxSum of type int and initialize it to INT_MIN. Include the header <climits> to use INT_MIN.

DSA C++

#include 
// Add global variable maxSum initialized to INT_MIN
// Your code here

Hint

Include <climits> at the top. Then declare int maxSum = INT_MIN; outside main().

3

Implement Recursive Function to Find Maximum Path Sum

Write a recursive function called maxPathSumHelper that takes a TreeNode* called node and returns an int. It should calculate the maximum path sum starting from node going down. Update the global maxSum with the maximum path sum found including both left and right children. Use the logic:
1. If node is nullptr, return 0.
2. Recursively get left and right max sums, but ignore negatives by using max(0, ...).
3. Calculate current max path sum as node->val + left + right.
4. Update maxSum if current max path sum is greater.
5. Return node->val + max(left, right).

DSA C++

#include 
// Implement maxPathSumHelper function below
// Your code here

Hint

Use recursion to get max sums from left and right children. Use max(0, ...) to ignore negative sums. Update maxSum with the sum including both children. Return the max path sum including the current node and one child.

4

Calculate and Print the Maximum Path Sum

In main(), call maxPathSumHelper with root to start the calculation. Then print the global variable maxSum using cout.

DSA C++

// Call maxPathSumHelper with root
// Print maxSum
// Your code here

Hint

Call maxPathSumHelper(root); to compute the max path sum. Then print maxSum using cout.

Practice

1. What does the term Maximum Path Sum in a binary tree mean?

easy

A. The sum of all node values in the tree

B. The largest sum of values along any path between two nodes in the tree

C. The maximum value of a single node in the tree

D. The sum of values from root to the deepest leaf only

Solution

1. Step 1: Understand the path definition

   A path in a binary tree can start and end at any nodes, not necessarily root or leaf.

2. Step 2: Define maximum path sum

   It is the highest sum of node values along any such path in the tree.

3. Final Answer:

   The largest sum of values along any path between two nodes in the tree -> Option B

4. Quick Check:

   Maximum path sum means highest sum on any path [OK]

Hint: Maximum path sum is any path, not just root to leaf [OK]

Common Mistakes:

• Confusing maximum path sum with sum of all nodes
• Thinking path must start at root
• Considering only leaf nodes for path ends

2. Which of the following C++ function signatures is correct for a helper function that returns the maximum path sum starting from a given node in a binary tree?

easy

A. int maxPathSumHelper(TreeNode* root, int& maxSum);

B. void maxPathSumHelper(TreeNode root, int maxSum);

C. int maxPathSumHelper(TreeNode root);

D. int maxPathSumHelper(TreeNode* root);

Solution

1. Step 1: Understand parameter passing

   The function needs to update maxSum globally, so it must be passed by reference.

2. Step 2: Check pointer usage

   TreeNode* is used to pass node pointers, not objects directly.

3. Final Answer:

   int maxPathSumHelper(TreeNode* root, int& maxSum); -> Option A

4. Quick Check:

   Use pointer and reference for maxSum [OK]

Hint: Pass maxSum by reference and node as pointer [OK]

Common Mistakes:

• Passing TreeNode by value instead of pointer
• Not passing maxSum by reference
• Using void return type instead of int

3. Consider the following binary tree:

    1
   / \
  2   3

What is the maximum path sum returned by the standard algorithm?

medium

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Calculate path sums including root

   Paths: 2->1->3 sum = 6, 2->1 sum = 3, 1->3 sum = 4.

2. Step 2: Identify maximum sum

   The maximum path sum is 6 from path 2->1->3.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   2+1+3 = 6 [OK]

Hint: Check all paths including both children and root [OK]

Common Mistakes:

• Considering only root-to-leaf paths
• Ignoring paths passing through root
• Adding only one child value

4. Given this buggy code snippet for maximum path sum, what is the main error?

int maxPathSumHelper(TreeNode* root, int& maxSum) {
  if (!root) return 0;
  int left = maxPathSumHelper(root->left, maxSum);
  int right = maxPathSumHelper(root->right, maxSum);
  int current = root->val + left + right;
  maxSum = max(maxSum, current);
  return root->val + max(left, right);
}

What is the bug?

medium

A. It does not ignore negative path sums

B. It returns sum of both children instead of max child

C. It updates maxSum incorrectly

D. It does not handle null root

Solution

1. Step 1: Analyze negative path sums handling

   The code adds left and right directly without ignoring negative sums, which can reduce maxSum.

2. Step 2: Correct approach for negatives

   Should use max(0, left) and max(0, right) to ignore negative sums.

3. Final Answer:

   It does not ignore negative path sums -> Option A

4. Quick Check:

   Negative sums must be ignored to maximize path sum [OK]

Hint: Use max(0, child) to ignore negative sums [OK]

Common Mistakes:

• Adding negative child sums reduces maxSum
• Returning sum of both children instead of max child
• Not checking for null root

5. Given the binary tree below, what is the maximum path sum?

       -10
       /  \
      9   20
          / \
         15  7

Choose the correct maximum path sum.

hard

A. 27

B. 35

C. 42

D. 15

Solution

1. Step 1: Calculate max path sums for subtrees

   Left subtree max path sum is 9. Right subtree max path sum includes 20 + 15 + 7 = 42.

2. Step 2: Consider paths through root

   Path through root: -10 + max(0,9) + max(0,15+20+7) = -10 + 9 + 42 = 41, less than 42.

3. Step 3: Identify maximum path sum

   The maximum path sum is 42 from path 15->20->7.

4. Final Answer:

   42 -> Option C

5. Quick Check:

   15+20+7 = 42 [OK]

Hint: Check all subtree sums and paths through root [OK]

Common Mistakes:

• Including negative root value in max path sum
• Ignoring paths not passing through root
• Adding left and right children without max(0, val)