## Binary tree traversal

02 Nov 2014

Here is a full binnary tree:

``````          1
/    \
/        \
2          5
/   \      /   \
3     4    6     7
/ \   / \  / \   / \
N  N  N  N  N  N  N  N
``````
• Pre-order Traversal

1. visit root first
2. visit left child by pre-order traversal
3. visit right child by pre-order traversal
``````1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
``````
• In-order Traversal

1. visit left child in in-order
2. visit root
3. visit right child in in-order
``````3 -> 2 -> 4 -> 1 -> 6 -> 5 -> 7
``````
• Post-order Traversal

1. visit left child in post-order
2. visit right child in post-order
3. visit root
``````3 -> 4 -> 2 -> 6 -> 7 -> 5 -> 1
``````

### Recursively

Traversal by recursion is very easy.

``````class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
``````
• Pre-order

``````class Solution:
def preorderTraversal(self, root):
res = []
if root:
res.append(root.val)
if root.left:
res.extend(self.preorderTraversal(root.left))
if root.right:
res.extend(self.preorderTraversal(root.right))
return res
``````
• In-order

``````class Solution:
def inorderTraversal(self, root):
res = []
if root:
if root.left:
res.extend(self.inorderTraversal(root.left))
res.append(root.val)
if root.right:
res.extend(self.inorderTraversal(root.right))
return res
``````
• Post-order

``````class Solution:
def postorderTraversal(self, root):
res = []
if root:
if root.left:
res.extend(self.postorderTraversal(root.left))
if root.right:
res.extend(self.postorderTraversal(root.right))
res.append(root.val)
return res
``````

### Iteratively

Traversing iteratively needs extra space instead of calling function recursively.

#### Pre-order Traversal

Pre-order is easy.

1. push root to stack
2. pop a node from stack
3. mark it as visited(put its value into result list), push its right and left child to stack if they are not `Nil`, push right first to make sure than left child will be poped first.
4. when stack has no node to pop, traversal is done.
``````class Solution:
# @param root, a tree node
# @return a list of integers
def preorderTraversal(self, root):
res = []
if root is None:
return res
stack = []
stack.append(root)
while stack:
item = stack.pop()
res.append(item.val)
if item.right:
stack.append(item.right)
if item.left:
stack.append(item.left)
return res
``````

#### In-order Traversal

1. Set next node to be visited to root.
2. If next node is not `Nil`, push it to stack, set next node to be visited to its left child
3. If next node is `Nil`, pop its parent node from stack, mark it as visited(put its value into result list), then set next node to be visited to its right brother node.
4. If next node is a child node and it is `Nil`, its parent has been visited, its grandfather node will be poped from the stack and be visited.
5. when stack has no node to be visited and next node is `Nil`, traversal is done.

steps:

1. set next node to root, `next` is 1
2. `next = 1` is not `Nil`, push 1 to stack, `stack = `, set `next` to its left child, `next = 2`
3. `next = 2` is not `Nil`, push 2 to stack, `stack = [1, 2]`, set `next` to its left child, `next = 3`
4. `next = 3` is not `Nil`, push 3 to stack, `stack = [1, 2, 3]`, set `next` to its left child, `next = Nil`
5. `next` is `Nil`, pop its parent 3 from stack, `stack = [1, 2]`, mark it as visited, `res = `, set `next` to its right child, `next = Nil` 6 `next` is `Nil`, pop a node, 2 from stack, mark it as visit, `stack = , res = [3, 2]`, next is the right child of poped node 2, it is 4.
6. `next = 4` is not `Nil`, push to stack, `stack = [1, 4]`, next is its left child, it is Nil.
7. `next` is `Nil`, 4 will be poped from stack and marked as visited, its right child is also `Nil`, set `next` to Nil;
8. `next` is `Nil`, another node 1 will be poped and mark as visited afterwards. `stack = []`, `res = [3, 2, 4, 1]`, `next` is 5.
9. 5 is similar with 2, and after go to step 8, `next is Nil`, which is the right child of 7 (similar to 4 in step 7)
10. `next` is `Nil`, but there is nothing in stack, traversal is done.
``````class Solution:
# @param root, a tree node
# @return a list of integers
def inorderTraversal(self, root):
res = []
if root is None:
return res
stack = []
next = root
while stack or next:
if next:
stack.append(next)
next = next.left
else:
mid = stack.pop()
res.append(mid.val)
next = mid.right
return res
``````

#### Post-order Traversal

Post-order is similar to in-order but more complicated.

We can trace to the leftmost node from a root node, like in-order.

When `next` is `Nil`, its parent node should be visited after right child. So we should not pop stack unless the right child of the top node in stack is `Nil` or has been visited.

We use a variable `last_visited` to mark the node marked visited last time.

So when `next` is `Nil`, check if the right child of the top node in stack is `Nil` or visited. If yes, pop it, mark it as visited(put its value into result list), set it to be the `last_visited`.

If not, set the right node to be the `next`. The right node will be set to `last_visited` when it has no right child or its right child is visited. So the parent will be visited afterwards.

``````class Solution:
# @param root, a tree node
# @return a list of integers
def postorderTraversal(self, root):
res = []
if root is None:
return res
next = root
stack = []
last_visited = None

while next or stack:
if next:
stack.append(next)
next = next.left
else:
right = stack[-1].right
if right is None or right == last_visited:
mid = stack.pop()
res.append(mid.val)
last_visited = mid
else:
next = right

return res
``````