# Share my iterative Python solution (post-order traversal)

• There are only a few iterative solutions for this problem. Here I share an iterative one.
The idea is to use post-order traversal. If a node's children have all been visited, that node is labelled as 'visited'. Lists are used to pass path sum of left / right sub-trees and then pass value up.
The code uses the knowledge that no test case of empty tree.

``````import sys
class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
maxPathSum = -sys.maxint - 1
stack = [(root, False, [0], [0], [0])]
while stack:
node, visited, parent, left, right = stack.pop()
if visited:
# all children visited, update parent value, ignore negative values
parent[0] = max(max(left[0], right[0]) + node.val, 0)
# update maximum path sum
maxPathSum = max(maxPathSum, left[0] + right[0] + node.val)
else:
# not visited, push back onto stack, set visited to True
stack.append((node, True, parent, left, right))
# push right and left child onto stack
if node.right:
stack.append((node.right, False, right, [0], [0]))
if node.left:
stack.append((node.left, False, left, [0], [0]))

return maxPathSum``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.