# python iterative post order traversal

• Hi All,

I couldn't find an iterative python solution ANYWHERE in the web. I thought I'd share mine and your comments and feedback will make it better. Feel free to post your own version.

The approach is to use post order traversal as a bottom up approach. We're building the height starting from the leaves. We're updating the parent's left and right height from the children's height. This leads me to constantly iterate through the stack. I don't think this is the best approach. Feedback for better approach is welcome :)

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""

if not root:
return 0

stack = [[root, False, "", 0, 0]]
diameter = 0

while stack:
node, visited, parent, left_height, right_height = stack.pop()

if visited:
#update stack
for i, row in enumerate(stack):

parent_node = row[0]
parent_visited = row[1]
parent_parent = row[2]
parent_left_height = row[3]
parent_right_height = row[4]

#if (parent == parent_node) and (node is not root): #if node's parent
if parent == parent_node:

#update left height or right height
if parent_node.left == node:
parent_left_height = max(parent_left_height, max(left_height,right_height) + 1)
stack[i] = [parent_node, parent_visited, parent_parent, parent_left_height, parent_right_height]
if parent_node.right == node:
parent_right_height = max(parent_right_height, max(left_height, right_height) + 1)
stack[i] = [parent_node, parent_visited, parent_parent, parent_left_height, parent_right_height]
print parent_left_height, parent_right_height
#print "1", parent_node.left.val

diameter = max(diameter, left_height + right_height)
else:
stack.append([node, True, parent, left_height, right_height])
if node.right: stack.append([node.right, False, node, left_height, right_height])
if node.left: stack.append([node.left, False, node, left_height, right_height ])

return diameter
``````

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