# Non recursive postorder traversal of binary tree

### 1. Using 1 stack

O(n) time, O(n) space

The initial setting stack is empty, and the current node is the root node

Perform the following operations until the stack is empty and the current node is empty:

- Stack the current node and set the left child as the current node until the current node is empty.
- Make the current node stack[-1]
- If the right child of the current node is empty or equal to prev (indicating that the right subtree has been accessed)

– access the current node and exit the stack

– set prev = current node

– make the current node = None - Otherwise, set the right child as the current node

stack = [] node = root while node and stack: if node: stack.append(node) node = node.left else: node = stack[-1] if not node.right or node.right == prev: print(node.val) stack.pop() node = None else: node = node.right

### 2. Using 2 stacks

O(n) time, O(n) space

stack: used to store and traverse child nodes. Initialization = [root]

Path: records the path from the root node to the current node

Do the following until stack is empty:

- node = stack[-1]
- If the path stack top element is not node:

– the current node, the right child and the left child (if not empty) are stack ed in turn - If the stack and path stack top elements are the same:

– access node

– stack and path pop up the top of the stack

stack = [root] path = [] while stack: node = stack.pop() if path and path[-1] == node: path.pop() print(node.val) else: path.append(node) if node.right: stack.append(node.right) stack.append(node) if node.left: stack.append(node.left)

### 3. Using no stacks (Morris traversal)

O(n) time, O(1) space

Based on the middle order morris traversal, the traversal order is changed from "left root right" to "left root right". One method is to add a dummy node so that the root node is its left child, then use the reverse auxiliary function to reverse the "root to the rightmost" part of each layer, traverse the layer, and then reverse the recovery structure. The source of the picture is leetcode user xruzty of This article.

Create a dummy node and set its left child to root

Initialize node = dummy

Do the following until node is empty:

- If the left child of the current node node is not empty, find the precursor node traversed in the middle order, and the rightmost descendant of the left child

– if the right child of the predecessor node is empty, set the right child of the predecessor node as the current node. Update node = node.left

– if the right child of the predecessor node is not empty (it is the current node; it means that the layer before the predecessor node has been accessed in the uplink process):- Reverse node.left to prev
- Traverse access prev to node.left
- Reverse again to restore the original structure
- Restore tree structure: prev.right = None
- node = node.right

- If the left child of node is empty, update node = node.right

def reverse(start, end): if start == end: return prev = start node = start.right while prev != to: tmp = node.right node.right = prev prev = node node = tmp dummy = TreeNode(None) dummy.left = root node = dummy while node and node.val: if node.left: prev = node.left while prev.right and prev.right != node: prev = prev.right if not prev.right: prev.right = node node = node.left else: reverse(node.left, prev) tmp = prev while tmp != node.left: print(tmp.val) tmp = tmp.right print(tmp.val) # print node.left.val prev.right = None node = node.right else: node = node.right

reference material:

https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45648/three-ways-of-iterative-postorder-traversing-easy-explanation