Maximum Path Sum in Binary Tree in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the definition of the Maximum Path Sum in a Binary Tree?

It is the largest sum of values obtained by any path in the binary tree. A path can start and end at any node, and must follow parent-child connections.

intermediate

Why do we consider negative values when calculating Maximum Path Sum?

Because nodes can have negative values, and including them might reduce the total sum. We ignore paths with negative sums by choosing zero instead.

intermediate

In the Maximum Path Sum problem, what does the recursive function typically return?

It returns the maximum sum of a path starting from the current node and extending downwards to one child, or zero if all are negative.

intermediate

How do we update the global maximum path sum during recursion?

At each node, we calculate the sum of the node's value plus the maximum sums from left and right children. If this sum is greater than the current global max, we update it.

beginner

What is the time complexity of the Maximum Path Sum algorithm in a binary tree?

The time complexity is O(n), where n is the number of nodes, because we visit each node once during the recursion.

What does a path in the Maximum Path Sum problem represent?

A A sequence of nodes connected by parent-child links

B Any random nodes in the tree

C Only leaf nodes

D Nodes connected horizontally

A path must follow parent-child connections, not random or horizontal nodes.

If a node's left and right child paths have negative sums, what should the recursion return for that node?

A Negative infinity

B The node's value only

C The sum of both children plus node's value

D Zero or the node's value, whichever is larger

We ignore negative sums by choosing zero to avoid reducing the path sum.

When do we update the global maximum path sum during recursion?

A At every node, considering node + left + right sums

B Only at leaf nodes

C Only at the root node

D After recursion finishes

We update at every node by checking the sum of node plus left and right child paths.

What is the base case for the recursion in Maximum Path Sum?

A When the node is a leaf, return its value

B When the node has two children

C When the node is null, return zero

D When the node value is negative

For null nodes, we return zero to stop recursion.

What is the overall time complexity of the Maximum Path Sum algorithm?

A O(n^2)

B O(n)

C O(log n)

D O(n log n)

Each node is visited once, so time complexity is O(n).

Explain how the recursive function helps find the Maximum Path Sum in a binary tree.

Think about how each node contributes to the path and how recursion combines results.

Describe the role of the global variable in the Maximum Path Sum algorithm.

Why do we need to keep track of the best path sum globally?