I'm brushing up on leet code tree questions and every solution of Iterative Postorder Traversal of Binary Tree in Python type problems seem to use recursion.

Since there is no tail recursion in python, I believe iterative algorithm is faster because it takes less time to move around a stack than to jump through stack call frames.

Additionally I believe the iterative approach uses less memory because tracking just one stack takes up less space than the call frame stack from recursion.

I understand the typical approach to postorder iterative traversal takes 2 stacks and while loops so it seems to complicated.

However, there is an algorithm to use just 1 stack and while loop.

Here it is:

def postorderIterative(root):
            curr = root
            stack = []
            while current or stack:
                if current:
                    stack.append[current]
                    current = current.left
                else:
                    tmp = stack[-1].right
                    if not tmp:
                        tmp = stack.pop()
                        #process postorder here
                        while stack and tmp == stack[-1].right:
                            tmp = stack.pop()
                            #process postorder here
                    else:
                        current = tmp

credit and explanation goes to here

Is there any reason why most video solutions seem to use recursive postorder traversal more than iterative even though iterative is better? is it because recursive is easier to understand?

It seems that with a big enough test case the recursive may fail in any call so I tend to always do iterative. Is this a valid approach?

I literally cannot find an iterative solution video to leet code: 543. Diameter of Binary Tree

these are all recursive and thus suboptimal, even though they say it is optimal.

Please let me know if I am wrong and why. If not. please let me know as well. I am here to learn!

CodePudding user response：

Both the iterative and recursive implementations have the same time and space complexity. The difference in running time is insignificant in terms of big O. When speaking of optimal, people usually mean the time/space complexity is optimal.

Secondly, the call stack limitation will only be a problem for a binary tree that has a height that goes into the hundreds. If a tree of such height were balanced, it would have more nodes than there are atoms in the universe. So we would only get into stack limitations when the binary tree is awfully skewed, which would make it rather useless for a real life problem. In short, I don't think the call stack limitation is such an important argument here.