# Coding Questions - Tree Basics¶

As most binary tree problems, you want to solve this recursively.

## LeetCode 145. Binary Tree Postorder Traversal¶

Basic Tree Operations:

Just adjust the time to evaluate the node, each recursive method is a stack operation. To seperate the inorder and preorder iterative call, just print current value at different time.

1. In-Order Traversal

Recursive:

```def inorder_recurr(root, res):
if root:
traverse_recurr(root.left, res)
res.append(root.val)
traverse_recurr(root.right, res)
return res
```

Iterative:

```def inorder_iterative(root, res):
res = []
stack = []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
return stack
node = stack.pop()
res.append(node.val)
root = node.right
return res
```
2. Pre-Order Traversal

Recursive:

```def inorder_recurr(root, res):
if root:
res.append(root.val)
traverse_recurr(root.left, res)
traverse_recurr(root.right, res)
return res
```

Iterative:

```def preorder_traverse_stack_0(root):
stack = []
res = []
stack.append(root)
while(stack):
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res

def inorder_iterative_1(root, res):
res = []
stack = []
while True:
while root:
res.append(node.val)
stack.append(root)
root = root.left
if not stack:
return stack
node = stack.pop()
root = node.right
return res
```
3. Post-Order Traversal

According to oberservation, the post order is just the preorder, put the root after child tree. Another interpretation is the print node method is called after stack call.

Recursive:

```def inorder_recurr(root, res):
if root:
res.append(root.val)
traverse_recurr(root.left, res)
traverse_recurr(root.right, res)
return res
```

Iterative:

```def postorder_traverse_stack(root):
stack = []
stack2 = []
res = []
stack.append(root)
while stack:
node = stack.pop()
stack2.append(node.val)  # res.append(node.val) just use another stack to hold the results instead of printing it
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
for val in stack2[::-1]:
res.append(val)
return res

def postorder_traverse_stack(root):
stack = []
res = []
while True:
while root:
if root.right:
stack.append(root.right)
stack.append(root)
root = root.left
if not stack:
return res
root = stack.pop()
if root.right and stack and stack[-1] == root.right:
stack.pop()
stack.append(root)
root = root.right
else:
res.append(root.val)
root = None
return res
```
1. BFS

Recursive::

# If you want to use recursive, you have to find the right varaible to pass between # different values

# the list that passes between levels are final list # find the statement to update that final list def recursive(res, root, level):

if not root:

return

if level < len(res):

res[level].append(root.val)

else:

res.append([root.val])

recursive(res, root.left, level+1) recursive(res, root.right, level+1)

Iterative：：
def BFS(self, root):
if not root:

return []

final = [] queue = [] queue.append(root) while queue:

res = [] # we have queue and we need to get each level # this is done by get the size of queue which is the size of the level n = len(queue) while(n):

node = queue.pop(0) res.append(node.val) if node.left:

queue.append(node.left)

if node.right:

queue.append(node.right)

n -= 1

final.append(res)

return final

2. Morris Traversal
class Codec_0:
def serialize(self, root):

“”“Encodes a tree to a single string.

type root: TreeNode str

“”” if not root:

return ‘’

queue = [root] res = [] while queue:

node = queue.pop(0) if node != None:

res.append(node.val) queue.append(node.left) queue.append(node.right)
else:
res.append(‘None’)

return ‘[‘+ ‘, ‘.join(res)+’]’

def deserialize(self, data):

“”“Decodes your encoded data to tree.

type data: str TreeNode

“”” data = data.strip(‘[]{}’).split(‘,’) if not data:

return None

root = TreeNode(data[0]) queue = [root] i = 0 while i < len(data) and queue:

node = queue.pop(0) if i + 1 < len(data) and data[i+1] != ‘None’:

node.left = TreeNode(data[i+1]) queue.append(node.left)
if i + 2 < len(data) and data[i + 2] != ‘None’:
node.right = TreeNode(data[i+2]) queue.append(node.right)

i += 2

return root

class Codec:
def serialize(self, root):

“”“Encodes a tree to a single string.

type root: TreeNode str

“”” if not root:

return ‘’

stack = [root] res = []

while stack:
while root:
res.append(root.val) stack.append(root) root = root.left

res.append(‘None’) node = stack.pop() if not node:

res.append(‘None’)
else:
root = node.right

return ‘[‘+ ‘, ‘.join(res)+’]’

def deserialize(self, data):

“”“Decodes your encoded data to tree.

type data: str TreeNode

“”” data = data.strip(‘[]{}’).split(‘,’) if not data:

return None

root = TreeNode(data[0]) stack = [root] x= stack[-1] i = 1 while i < len(data):

while i < len(data) and data[i] != ‘None’:
root.left = TreeNode(data[i]) root = root.left stack.append(root) i += 1
while i < len(data) and data[i] == ‘None’ and stack:
root = stack.pop() i += 1
if i < len(data):
root.right = TreeNode(data[i]) root = root.right stack.append(root) i += 1

return x