Question

c++ write a iterative post order traversal using 1 stack and (passing a Node pointer to the root of the binary search to the parameter).

Answer 1

Sol.

We can implement function of post order traversal using only 1 stack.

def postorderTraversal(self, root: TreeNode) -> List[int]:
retu = [] // Empty List
if not root: return ret // Return list if root is null
st = [root] * 2 // push the root in the stack 2 times
while st: // while stack not empty
cur = st.pop() // save stack top in cur variable
if st and st[-1] is cur: // if stack is empty and stack top is cur oherwise goto else part (push cur.val in list ret)
if cur.right: // if current right is not null
st += [cur.right] * 2 //push 2 times cur.left in stack
if cur.left: // if current left is not null
st += [cur.left] * 2 //push 2 times cur.right in stack
else:
ret.append(cur.val)
return ret // finally return list ret.