# Binary Tree Postorder Traversal

StackTreeMorris

## # Definition for a Binary Tree Node

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

1
2
3
4
5

## # Solution

Let $n$ be the number of nodes in the tree.

### # Recursion

Complexity

time: $O(n)$
space: $O(n)$

def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []

def postorder(node: TreeNode):
if not node: return
postorder(node.left)
postorder(node.right)
res.append(node.val)

postorder(root)
return res

1
2
3
4
5
6
7
8
9
10
11

Recursive solution is trivial, could you do it iteratively?

### # Iteration

Complexity

time: $O(n)$
space: $O(n)$

#### # Two Stacks

From bottom to top, s1 stores root, left subtree and right subtree, s2 stores root and traverses the right subtree before the left subtree, res reverses s2 and stores left subtree, right subtree and root.

def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root: return []
res = []
s1, s2 = [root], []

while s1:
node = s1.pop()
s2.append(node.val)
if node.left:
s1.append(node.left)
if node.right:
s1.append(node.right)

while s2:
res.append(s2.pop())

return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#### # One Stack (REDO)

pre stores the current node once the right subtree is done visiting.

Complexity

time: $O(n)$
space: $O(n)$

def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
pre = None

while root or stack:
# keep visiting the left subtree
while root:
stack.append(root)
root = root.left
root = stack.pop()
# right subtree is done visiting
if not root.right or root.right == pre:
res.append(root.val)
pre = root
root = None
# keep visiting the right subtree
else:
stack.append(root)
root = root.right
return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21