Maximum Path Sum in Binary Tree
Medium Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Determine the Maximum Path Sum in a Binary Tree, Binary Tree, Depth-First Search, Recursion, Tree Traversal, Time Complexity, Space Complexity, complexity analysis, dynamic programming, graph algorithms, binary tree, recursion, tree traversal, Maximum Path Sum, Fractional Knapsack.
Maximum Path Sum in a Binary Tree Problem Statement Given a non empty binary tree, find the maximum path sum. A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent child connections. The path does not need to pass through the root. A path must contain at least one node and does not need to be symmetric. Input Specification The input will be a space separated string representing the binary tree in level order traversal. A value of 1 indicates a null node. Output Specification Return an integer representing the maximum path sum in the binary tree. Examples Example 1: Input: 10 9 20 1 1 15 7 Tree Representation: Output: 42 Explanation: The path 15 20 7 has the greatest sum, which is 15 + 20 + 7 = 42. Example 2: Input: 2 2 1 Tree Representation: Output: 2 Explanation: The path starting and ending at the node with value 2 has the greatest sum, which is 2.