Binary Tree Maximum Path Sum
Understand and solve the interview question "Binary Tree Maximum Path Sum".
We'll cover the following...
Description
A path in a binary tree is defined as:
A sequence of nodes such that each pair of adjacent nodes must have an edge connecting them. A node can only be included in a path at most once. Moreover, including the root in the path is not compulsory.
The path sum can be calculated by adding up all nodes’ values in the path. To solve this problem, we will calculate the maximum path sum given the root of a binary tree so that there won’t be any greater path than it in the tree.
Example
Let’s discuss the example below:
Coding exercise
import {TreeNode} from './TreeNode.js'class Solution{constructor(){}maxPathSum(root) {}}
Solution
We’ll start by simplifying the problem and looking at the implementation of the max_contrib(node) function which takes a node as an argument and computes a maximum contribution that this node and one or ...