#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/trees/binary-tree-maximum-path-sum-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/trees/binary-tree-maximum-path-sum-implementation

Repovive

LeetCode 124 Binary Tree Maximum Path Sum - Implementation - Trees | Pattern 22: LeetCode Interview Patterns | Repovive

Repovive.

Pattern 22: LeetCode Interview Patterns24 sections · 736 units32h total

Open in Course

LeetCode 124 Binary Tree Maximum Path Sum - Implementation

The approach

Post-order traversal. Track max path sum globally, return gain upward.

function maxPathSum(root): result = float('-inf')

def maxGain(node):
    nonlocal result
    if not node:
        return 0
    leftGain = max(maxGain(node.left), 0)
    rightGain = max(maxGain(node.right), 0)
    pathSum = node.val + leftGain + rightGain
    result = max(result, pathSum)
    return node.val + max(leftGain, rightGain)

maxGain(root)
return result

$O(n)$ time, $O(h)$ space.