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.