Compute maximum path sum in binary tree

Q: Compute maximum path sum in binary tree

This is a Coding & Algorithms interview question from ByteDance for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given the root of a binary tree where each node contains an integer value (which may be negative), return the maximum possible sum of values along any path in the tree.

A path is defined as a sequence of nodes where each pair of adjacent nodes in the sequence is connected by a parent-child edge. The path:

Can start and end at any nodes in the tree.
Must contain at least one node.
Cannot jump between branches; it always follows child pointers up or down.

For example, in the tree:

9 20 /
15 7

The maximum path sum is 42, using the path 15 -> 20 -> 7.

Design an algorithm to compute this maximum path sum. Aim for O(n) time, where n is the number of nodes in the tree.

Compute maximum path sum in binary tree

Comments (0)