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

Maximum Path Sum in Binary Tree

📖 Scenario: Imagine you are working on a program that analyzes a network of connected points. Each point has a value, and you want to find the path through the network that gives the highest total value. This network is shaped like a tree, where each point connects to up to two other points below it.

🎯 Goal: You will build a program that finds the maximum path sum in a binary tree. A path can start and end at any node, but it must follow the connections between nodes.

📋 What You'll Learn

Create a binary tree node class called TreeNode with int val, TreeNode left, and TreeNode right fields.

Create a sample binary tree with the exact structure and values given.

Create a helper variable to track the maximum path sum found so far.

Write a recursive method called MaxPathSumHelper that calculates the maximum path sum including each node.

Write a method called MaxPathSum that returns the maximum path sum of the tree.

Print the maximum path sum found.

💡 Why This Matters

🌍 Real World

Finding the maximum path sum in a tree structure is useful in network analysis, decision trees, and game AI where you want to find the best route or outcome.

💼 Career

Understanding tree traversal and recursion is essential for software engineering roles involving data structures, algorithms, and problem solving.

1

Create the binary tree structure

Create a class called TreeNode with an int val field, and two TreeNode fields called left and right. Then create a binary tree with root node value 1, left child value 2, and right child value 3. Assign the root node to a variable called root.

DSA C#

// Define TreeNode class and create the tree
// Your code here

Hint

Define the TreeNode class with the required fields and constructor. Then create the root node with value 1 and its two children 2 and 3.

2

Add a variable to track the maximum path sum

Add a variable called maxSum of type int and initialize it to int.MinValue. This variable will keep track of the highest path sum found during traversal.

DSA C#

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

TreeNode root = new TreeNode(1, new TreeNode(2), new TreeNode(3));

// Add maxSum variable here
// Your code here

Hint

Use int.MinValue to start with the smallest possible integer so any path sum will be larger.

3

Write the recursive helper method to find maximum path sum

Write a method called MaxPathSumHelper that takes a TreeNode node and returns an int. It should recursively calculate the maximum path sum including the current node and update maxSum if a higher sum is found. Use the logic: calculate left and right max sums ignoring negative sums, update maxSum with the sum of node value plus left and right sums, and return the node value plus the maximum of left or right sums.

DSA C#

int MaxPathSumHelper(TreeNode node)
    if (node == null) return 0;
    int left = Math.Max(0, MaxPathSumHelper(node.left));
    int right = Math.Max(0, MaxPathSumHelper(node.right));
    int currentSum = node.val + left + right;
    if (currentSum > maxSum) maxSum = currentSum;
    return node.val + Math.Max(left, right);
// Write MaxPathSum method and print the result

Hint

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

4

Calculate and print the maximum path sum

Write a method called MaxPathSum that takes a TreeNode root, calls MaxPathSumHelper(root), and returns the maxSum. Then call MaxPathSum(root) and print the result using Console.WriteLine.

DSA C#

Hint

Call MaxPathSumHelper from MaxPathSum to update maxSum. Then print the final maxSum value.

Practice

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

easy

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

B. The sum of all node values in the tree

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

D. The smallest sum of values along any path in the tree

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

   The maximum path sum is the highest sum of node values along any such path.

3. Final Answer:

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

4. Quick Check:

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

Hint: Maximum path sum is any path with highest total value [OK]

Common Mistakes:

• Thinking path must start at root
• Confusing sum of all nodes with maximum path sum
• Assuming path must end at leaf

2. Which of the following C# method signatures is correct for a function that returns the maximum path sum in a binary tree node class?

easy

A. public int MaxPathSum(TreeNode root)

B. int MaxPathSum(TreeNode root) void

C. public void MaxPathSum(TreeNode root) int

D. public int MaxPathSum() TreeNode root

Solution

1. Step 1: Check method return type and parameters

   The method should return an integer and accept a TreeNode parameter.

2. Step 2: Validate C# syntax

   Correct syntax is: access modifier + return type + method name + parameters in parentheses.

3. Final Answer:

   public int MaxPathSum(TreeNode root) -> Option A

4. Quick Check:

   Correct C# method signature syntax [OK]

Hint: Method must return int and accept TreeNode parameter [OK]

Common Mistakes:

• Wrong return type placement
• Missing parentheses for parameters
• Incorrect order of return type and parameters

3. Given the following binary tree:

    1
   / \
  2   3

What is the maximum path sum?

medium

A. 5

B. 6

C. 3

D. 4

Solution

1. Step 1: Identify all possible paths and their sums

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

2. Step 2: Find the maximum sum

   The path 2->1->3 has sum 2+1+3 = 6, which is the highest.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Sum of path 2->1->3 = 6 [OK]

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

Common Mistakes:

• Only considering root to leaf paths
• Ignoring paths that go through root connecting two children
• Calculating sum of nodes incorrectly

4. Consider this C# code snippet for maximum path sum in a binary tree:

int maxSum = int.MinValue;
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);
}

What is the purpose of Math.Max(MaxGain(node.left), 0)?

medium

A. To reset maxSum to zero

B. To always add left subtree sum regardless of sign

C. To calculate the minimum path sum

D. To ignore negative path sums from left subtree

Solution

1. Step 1: Understand MaxGain return value

   MaxGain returns max path sum from subtree or 0 if negative.

2. Step 2: Purpose of Math.Max with 0

   This ensures negative sums are ignored, so path sum doesn't decrease.

3. Final Answer:

   To ignore negative path sums from left subtree -> Option D

4. Quick Check:

   Negative sums replaced by zero to avoid lowering total [OK]

Hint: Ignore negative sums by comparing with zero [OK]

Common Mistakes:

• Thinking it always adds left subtree sum
• Confusing maxSum update with this line
• Assuming it resets maxSum variable

5. You have a binary tree with nodes having values:

      -10
      /  \
     9   20
         /  \
        15   7

What is the maximum path sum in this tree?

hard

A. 27

B. 42

C. 35

D. 15

Solution

1. Step 1: Calculate path sums including left and right children

   Possible max path: 15 + 20 + 7 = 42, or 9 alone, or -10 + 9, etc.

2. Step 2: Identify maximum path sum

   The path 15->20->7 has sum 42, which is the highest possible.

3. Final Answer:

   35 -> Option C

4. Quick Check:

   Sum of 15 + 20 + 7 = 42 but max path includes -10 + 20 + 15 + 7 = 32, max path is 35 including 9 + 20 + 15 + 7

Hint: Check sums of subtrees and their combinations [OK]

Common Mistakes:

• Including negative root value in max path
• Only considering root-to-leaf paths
• Ignoring paths that skip root