Binary Tree Traversal

btree_traversal.py

# IN-ORDER
def in_order_iterative(root):
  stack = []
  visited = []
  while root or stack:
    while root:
      stack.append(root)
      root = root->left
    root = stack.pop()
    visited.append(root->val)
    root = root->right
    
def in_order_recursive(root):
  if not root:
    return
  inorder_recursive(root->left)
  visited.append(root->val)
  inorder_recursive(root->right)
  

# PRE-ORDER
def pre_order_iterative(root):
    visited = []
    stack = [root]
    while stack:
        root = stack.pop()
        if root:
            visited.append(root.val)
            stack.append(root.right)
            stack.append(root.left)
    return visited
  
def pre_order_recursive(root, visited):
    if not root:
        return
    visited.append(root.val)
    pre_order_recursive(root.left, visited)
    pre_order_recursive(root.right, visited)

# POST-ORDER
def post_order_iterative(root):
    visited = []
    if not root:
        return visited
    stack = [root]
    while stack:
        root = stack.pop()
        visited.append(root.val)
        if root.left:
            stack.append(root.left)
        if root.right:
            stack.append(root.right)
    visited.reverse()
    return visited
    
def post_order_recursive(root):
    if not root:
        return
    post_order_recursive(root.left, visited)
    post_order_recursive(root.right, visited)
    visited.append(root.val)