0%

Convert Recursive algo into Non-recursive

Pre

Before we try to convert any recursive algo into non-recursive, we should be familiar to recursive and non-recursive version of binary tree traversal.
Read binary tree traversal to recap.

Key points

  1. The idea is use stack in heap to mimic the behavior of function call stack.
  2. For post-order traversal, since we need to update parent’s state from child node, we will need to push state of parent along with child node into stack. We will explain this later with example.

Post order

Code skeleton

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
rst = []
stack, cur = [], root
while cur or stack:
while cur:
# Push current node
stack.append(cur)
# move to left or right child
cur = cur.left or cur.right
# all child is processed.
cur = stack.pop()
# update current state based on state from child nodes
rst.append(cur.val)
# upload state to parent
# ...

# Move to right node or previous level
if stack and stack[-1].left == cur:
cur = stack[-1].right
else:
cur = None
return rst
  1. Lowest Common Ancestor of a Binary Tree
    Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
'''
# Recursive
def dfs(cur):
if cur is None: return 0, None
cnt_l, node_l = dfs(cur.left)
cnt_r, node_r = dfs(cur.right)
if cnt_l == 2: return 2, node_l
if cnt_r == 2: return 2, node_r

if (cnt_l+cnt_r+(cur.val in [p.val, q.val])) == 2: return 2, cur

return (1, cur) if cur.val in [p.val, q.val] else ((cnt_l, node_l) if cnt_l else (cnt_r, node_r))
return dfs(root)[1]
'''

# Non-recursive
ret = [0] * 4 # cnt_l, node_l, cnt_r, node_r
stack, cur = [], ((root, [0] * 4), ret, 'l') # Carry all necessary data for current node and parent node
while cur[0][0] or stack:
while cur[0][0]:
stack.append(cur)
if cur[0][0].left: cur = ((cur[0][0].left, [0]*4), cur[0][1], 'l')
else: cur = ((cur[0][0].right, [0]*4), cur[0][1], 'r')
# Pop and unpack node and state
# ((cur_node, cur_state), (parent...), dir)
(node, (cnt_l, node_l, cnt_r, node_r)), p_state, dir = stack.pop()

# Compute local state based on state from childs
if cnt_l == 2: my_ret = 2, node_l
elif cnt_r == 2: my_ret = 2, node_r
elif (cnt_l+cnt_r+(node.val in [p.val, q.val])) == 2: my_ret = 2, node
else: my_ret = (1, node) if node.val in [p.val, q.val] else ((cnt_l, node_l) if cnt_l else (cnt_r, node_r))

# Upload state to parent
if dir == 'l': p_state[:2] = my_ret
else: p_state[2:] = my_ret

# :) Move to right or previous level
if stack and stack[-1][0][0].left == node:
cur = ((stack[-1][0][0].right, [0] * 4), stack[-1][0][1], 'r')
else:
cur = ((None, None), (None, None), None)

return ret[1]

More example