DP on Trees Maximum Path Sum in DSA C - Time & Space Complexity

Time Complexity: DP on Trees Maximum Path Sum

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the maximum path sum in a tree grows as the tree gets bigger.

How does the number of steps change when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int max(int a, int b) { return (a > b) ? a : b; }

int maxPathSumUtil(struct Node* root, int* res) {
    if (root == NULL) return 0;
    int left = max(0, maxPathSumUtil(root->left, res));
    int right = max(0, maxPathSumUtil(root->right, res));
    *res = max(*res, left + right + root->val);
    return max(left, right) + root->val;
}

int maxPathSum(struct Node* root) {
    int res = INT_MIN;
    maxPathSumUtil(root, &res);
    return res;
}
    

This code finds the maximum sum of values on any path in a binary tree by visiting each node once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls visiting each node once.
• How many times: Exactly once per node in the tree.

How Execution Grows With Input

As the number of nodes grows, the function visits each node once, doing a fixed amount of work per node.

Input Size (n)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The work grows directly with the number of nodes, so doubling nodes roughly doubles work.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the maximum path sum grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "The recursion might visit nodes multiple times, so it could be slower than linear."

[OK] Correct: Each node is visited once because the recursion only goes down each branch once, so no repeated work happens.

Interview Connect

Understanding this linear time complexity helps you explain how efficient your tree algorithms are, a key skill in interviews.

Self-Check

"What if the tree was very unbalanced, like a linked list? How would the time complexity change?"

Practice

1. What does the "Maximum Path Sum" in a tree represent in the context of dynamic programming on trees?

easy

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

B. The number of nodes in the longest path of the tree

C. The sum of all node values in the tree

D. The height of the tree

Solution

1. Step 1: Understand the problem definition

   The maximum path sum is about finding the path between any two nodes that yields the highest sum of node values.

2. Step 2: Differentiate from other tree properties

   Unlike longest path or height, maximum path sum focuses on the sum of node values, not count or depth.

3. Final Answer:

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

4. Quick Check:

   Maximum path sum = largest node value sum [OK]

Hint: Maximum path sum is about sums, not counts or heights [OK]

Common Mistakes:

• Confusing maximum path sum with longest path length
• Thinking it is the sum of all nodes
• Mixing it up with tree height

2. Which of the following is the correct base case initialization for a recursive function computing maximum path sum in a binary tree node in C?

easy

A. if (node == NULL) return INT_MIN;

B. if (node == NULL) return -1;

C. if (node == NULL) return 1;

D. if (node == NULL) return 0;

Solution

1. Step 1: Understand base case for null nodes

   For maximum path sum, null nodes should contribute 0 to the path sum as they do not add any value.

2. Step 2: Choose appropriate return value

   Returning 0 ensures that null nodes do not affect the sum and allows the recursion to proceed correctly.

3. Final Answer:

   if (node == NULL) return 0; -> Option D

4. Quick Check:

   Base case returns 0 to represent no contribution from null nodes [OK]

Hint: Use 0 for null nodes to avoid affecting sums [OK]

Common Mistakes:

• Returning INT_MIN which can cause incorrect sums
• Returning positive values for null nodes
• Returning 1 or -1 which are arbitrary and incorrect

3. Consider the following C code snippet for maximum path sum in a binary tree node structure. What is the output printed by printf("%d", maxSum); after calling maxPathSum(root); on the tree below?

Tree structure:
1
/ \\
2 3

typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

int maxSum = INT_MIN;

int maxPathSumUtil(Node* root) {
    if (!root) return 0;
    int left = maxPathSumUtil(root->left);
    int right = maxPathSumUtil(root->right);
    int maxSingle = (left > right ? left : right) + root->val;
    int maxTop = (left + right + root->val);
    if (maxTop > maxSum) maxSum = maxTop;
    return maxSingle > root->val ? maxSingle : root->val;
}

int maxPathSum(Node* root) {
    maxSum = INT_MIN;
    maxPathSumUtil(root);
    return maxSum;
}

medium

A. 3

B. 5

C. 6

D. 4

Solution

1. Step 1: Calculate max path sums for each node

   For node 2 and 3, maxSingle = 2 and 3 respectively, maxTop = 2 and 3. For root 1, left=2, right=3, maxSingle = max(2,3)+1=4, maxTop=2+3+1=6.

2. Step 2: Update maxSum and return final value

   maxSum updates to 6 at root. The function returns maxSum = 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

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

Hint: Sum path through root and children for max sum [OK]

Common Mistakes:

• Ignoring path through both children
• Returning maxSingle instead of maxSum
• Not updating global maxSum correctly

4. The following code attempts to compute the maximum path sum in a binary tree but has a bug. What is the bug?

int maxSum = INT_MIN;

int maxPathSumUtil(Node* root) {
    if (!root) return 0;
    int left = maxPathSumUtil(root->left);
    int right = maxPathSumUtil(root->right);
    int maxSingle = (left > right ? left : right) + root->val;
    int maxTop = (left + right + root->val);
    if (maxSingle > maxSum) maxSum = maxSingle;
    if (maxTop > maxSum) maxSum = maxTop;
    return maxSingle;
}

medium

A. It returns maxSingle without comparing it to root->val

B. It updates maxSum with maxSingle before maxTop, missing some max sums

C. It does not handle negative node values correctly

D. It returns maxSingle but should return maxTop

Solution

1. Step 1: Check return value correctness

   maxSingle should be max of (maxSingle, root->val) to handle negative values properly.

2. Step 2: Identify missing max comparison

   Without comparing maxSingle to root->val, the function may return a smaller sum than root's value alone.

3. Final Answer:

   It returns maxSingle without comparing it to root->val -> Option A

4. Quick Check:

   Return value must consider root->val for negatives [OK]

Hint: Always compare maxSingle with root->val before returning [OK]

Common Mistakes:

• Not handling negative values correctly
• Updating maxSum incorrectly
• Returning maxTop instead of maxSingle

5. Given a binary tree where nodes can have negative values, which approach correctly computes the maximum path sum using dynamic programming on trees?

hard

A. Use a recursive function that returns the maximum path sum including the current node and one child, update a global max with sum of node and both children, and handle negative values by comparing with zero

B. Use a recursive function that returns the maximum path sum including the current node and one child, update a global max with sum of node and both children, and handle negative values by comparing with the node's value itself

C. Use a recursive function that returns the sum of all nodes in the subtree, ignoring negative values, and update global max accordingly

D. Use a recursive function that returns the maximum path sum including the current node and both children always, without any comparison for negative values

Solution

1. Step 1: Understand handling of negative values

   Negative values require comparing max sums with the node's own value to avoid reducing sums by adding negative children.

2. Step 2: Correct recursive approach

   Return max path sum including current node and one child or node alone; update global max with sum of node and both children.

3. Final Answer:

   Use a recursive function that returns the maximum path sum including the current node and one child, update a global max with sum of node and both children, and handle negative values by comparing with the node's value itself -> Option B

4. Quick Check:

   Compare with node value to handle negatives correctly [OK]

Hint: Compare sums with node value itself to handle negatives [OK]

Common Mistakes:

• Ignoring negative values in sums
• Always adding both children without max checks
• Ignoring node's own value in comparisons