DSA C#programming

Maximum Path Sum in Binary Tree in DSA C#

Choose your learning style10 modes available

Learn Why Deep Visual Try Challenge Project Recall Time

Mental Model

Find the highest sum you can get by traveling along any path in the tree, where a path can start and end at any node.

Analogy: Imagine a mountain range where each peak has a height (value). You want to find the highest total height you can get by walking along connected peaks, but you can start and stop anywhere.

      [10]
      /   \
   [2]     [10]
   / \       \
 [20] [1]    [-25]
              /   \
           [3]     [4]

Dry Run Walkthrough

Input: Binary tree with nodes: 10, 2, 10, 20, 1, -25, 3, 4 as shown in the ascii picture

Goal: Find the maximum path sum anywhere in the tree

Step 1: Start at leaf node 20, max path sum from here is 20

20 (leaf) -> max path sum = 20

Why: Leaf nodes have max path sum equal to their own value

Step 2: At node 2, calculate max path sum including left child 20 and right child 1

2 -> left max=20, right max=1, max path through 2 = 20 + 2 + 1 = 23

Why: We consider paths through node 2 combining left and right children

Step 3: At node 10 (right child of root), right child is -25 with children 3 and 4

-25 -> left max=3, right max=4, max path through -25 = 3 + (-25) + 4 = -18

Why: Negative node reduces sum, so max path through -25 is less than children alone

Step 4: At node -25, max path sum from children is max(3,4) = 4, so max path from -25 is max(-25, -25+4, -25+3) = -21

-25 max path sum = -21

Why: We choose max single path to propagate upwards

Step 5: At node 10 (right child of root), max path sum including right child is max(10, 10 + 0, 10 + -21) = 10

10 max path sum = 10

Why: We ignore negative sums from right subtree to maximize path

Step 6: At root 10, max path sum through root combining left and right children is 23 (from left gain) + 10 (root) + 10 (right) = 43

Root max path sum = 43

Why: Combining left and right max paths with root gives maximum path sum

Result:

Maximum path sum = 43

Annotated Code

DSA C#

using System;

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;
    }
}

public class Solution {
    private int maxSum = int.MinValue;

    public int MaxPathSum(TreeNode root) {
        MaxGain(root);
        return maxSum;
    }

    private int MaxGain(TreeNode node) {
        if (node == null) return 0;

        // Recursively get max gain from left subtree
        int leftGain = Math.Max(MaxGain(node.left), 0);
        // Recursively get max gain from right subtree
        int rightGain = Math.Max(MaxGain(node.right), 0);

        // Price of the new path that passes through this node
        int priceNewPath = node.val + leftGain + rightGain;

        // Update maxSum if priceNewPath is better
        maxSum = Math.Max(maxSum, priceNewPath);

        // Return max gain if continue the same path
        return node.val + Math.Max(leftGain, rightGain);
    }
}

public class Program {
    public static void Main() {
        TreeNode root = new TreeNode(10,
            new TreeNode(2,
                new TreeNode(20),
                new TreeNode(1)),
            new TreeNode(10,
                null,
                new TreeNode(-25,
                    new TreeNode(3),
                    new TreeNode(4))));

        Solution sol = new Solution();
        int result = sol.MaxPathSum(root);
        Console.WriteLine(result);
    }
}

if (node == null) return 0;

stop recursion at leaf's child

int leftGain = Math.Max(MaxGain(node.left), 0);

calculate max gain from left subtree ignoring negative sums

int rightGain = Math.Max(MaxGain(node.right), 0);

calculate max gain from right subtree ignoring negative sums

int priceNewPath = node.val + leftGain + rightGain;

calculate max path sum passing through current node

maxSum = Math.Max(maxSum, priceNewPath);

update global max path sum if current path is better

return node.val + Math.Max(leftGain, rightGain);

return max gain to parent continuing one side path

OutputSuccess

Complexity Analysis

Time: O(n) because we visit each node once in the tree

Space: O(h) where h is the height of the tree due to recursion stack

vs Alternative: Naive approach might try all paths explicitly leading to exponential time; this uses recursion and pruning to achieve linear time

Edge Cases

Empty tree (root is null)

Returns int.MinValue as no path exists

DSA C#

if (node == null) return 0;

Tree with all negative values

Returns the maximum single node value since any path sum including multiple nodes would be smaller

DSA C#

int leftGain = Math.Max(MaxGain(node.left), 0);

Tree with single node

Returns the value of that single node as max path sum

DSA C#

if (node == null) return 0;

When to Use This Pattern

When asked to find the maximum sum path in a tree that can start and end anywhere, use a recursive depth-first search that tracks max sums including and passing through nodes.

Common Mistakes

Mistake: Not ignoring negative sums from children, which reduces the max path sum
Fix: Use Math.Max(childGain, 0) to ignore negative gains

Mistake: Returning sum of both children to parent, which breaks path definition
Fix: Return node value plus max of left or right gain only to continue one path upwards

Summary

Finds the highest sum of values along any path in a binary tree.

Use when you need the maximum sum path that can start and end at any node.

The key is to track max sums from children ignoring negative paths and update global max including both children.

Practice

(1/5)

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

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

Maximum Path Sum in Binary Tree in DSA C#

Practice

Solution

Step 1: Understand the path definition

Step 2: Define maximum path sum

Final Answer:

Quick Check:

Solution

Step 1: Check method return type and parameters

Step 2: Validate C# syntax

Final Answer:

Quick Check:

Solution

Step 1: Identify all possible paths and their sums

Step 2: Find the maximum sum

Final Answer:

Quick Check:

Solution

Step 1: Understand MaxGain return value

Step 2: Purpose of Math.Max with 0

Final Answer:

Quick Check:

Solution

Step 1: Calculate path sums including left and right children

Step 2: Identify maximum path sum

Final Answer:

Quick Check:

Ready to prove it?