# Iterative Traversal for a Binary Tree

## Problems

There are three ways to traverse a binary tree: preorder, inorder and postorder.

On Leetcode, there are three problems

### 144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,2,3]


### 94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,3,2]


### 145. Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes’ values.

Input: [1,null,2,3]
1
\
2
/
3

Output: [3,2,1]


## Though Process

• Use Stack
• Stack is LIFO
• Use stack to store the information of current node, right tree, left tree and action(“execute” or “go-to”)

## Code

### Pre-Order

Stack Order: right -> left -> node

# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

class StackCMD:
def __init__(self, node, cmd):
# cmd stores the current action
# only two values "go-to" and "exec"
# "go-to" go to a node, "exec" perform append node value to list
self.node, self.cmd = node, cmd

class Solution:

def preorderTraversal(self, root):
stack = []
res = []
# if none return an empty list
if root is None:
return res

curr_node = root
stack_cmd = StackCMD(curr_node, "go-to")
stack.append(stack_cmd)

while stack:
curr_cmd = stack.pop()
if curr_cmd.cmd == "exec":
res.append(curr_cmd.node.val)
else:
assert(curr_cmd.cmd == "go-to")
# make sure the cmd is either exec or go-to

# stack is LIFO so append order: right->left->node
# also check if right or left exists
curr_node = curr_cmd.node
if curr_node.right:
stack.append(StackCMD(curr_node.right, "go-to"))
if curr_node.left:
stack.append(StackCMD(curr_node.left, "go-to"))
stack.append(StackCMD(curr_node, "exec"))

return res


### In-Order

Stack Order: right -> node -> left

# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

class StackCMD:
def __init__(self, node, cmd):
# cmd stores the current action
# only two values "go-to" and "exec"
# "go-to" go to a node, "exec" perform append node value to list
self.node, self.cmd = node, cmd

class Solution:

def inorderTraversal(self, root):
stack = []
res = []
# if none return an empty list
if root is None:
return res

curr_node = root
stack_cmd = StackCMD(curr_node, "go-to")
stack.append(stack_cmd)

while stack:
curr_cmd = stack.pop()
if curr_cmd.cmd == "exec":
res.append(curr_cmd.node.val)
else:
assert(curr_cmd.cmd == "go-to")
# make sure the cmd is either exec or go-to

# stack is LIFO so append order: right->node->left
# also check if right or left exists
curr_node = curr_cmd.node
if curr_node.right:
stack.append(StackCMD(curr_node.right, "go-to"))
stack.append(StackCMD(curr_node, "exec"))
if curr_node.left:
stack.append(StackCMD(curr_node.left, "go-to"))

return res


### Post-Order

Stack Order: node -> right -> left

# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

class StackCMD:
def __init__(self, node, cmd):
# cmd stores the current action
# only two values "go-to" and "exec"
# "go-to" go to a node, "exec" perform append node value to list
self.node, self.cmd = node, cmd

class Solution:

def postorderTraversal(self, root):
stack = []
res = []
# if none return an empty list
if root is None:
return res

curr_node = root
stack_cmd = StackCMD(curr_node, "go-to")
stack.append(stack_cmd)

while stack:
curr_cmd = stack.pop()
if curr_cmd.cmd == "exec":
res.append(curr_cmd.node.val)
else:
assert(curr_cmd.cmd == "go-to")
# make sure the cmd is either exec or go-to

# stack is LIFO so append order: node->right->left
# also check if right or left exists
curr_node = curr_cmd.node
stack.append(StackCMD(curr_node, "exec"))
if curr_node.right:
stack.append(StackCMD(curr_node.right, "go-to"))
if curr_node.left:
stack.append(StackCMD(curr_node.left, "go-to"))

return res