Depth First Search

Iterative

In-order (LPR)

Time $θ(n)$, Space $θ(h)$

Python

# q -> prime number (to avoid overflow)
def inOrder(root):
    if root == None:
        return
    stack = []
    curr = root
    while curr:
        stack.append(curr)
        curr = curr.left
    while stack:
        curr = stack.pop()
        print(curr.val)
        curr = curr.right
        while curr:
            stack.append(curr)
            curr = curr.left

Pre-order (PLR)

Time $θ(n)$, Space $θ(n)$

Python

def preOrder(root):
    if root == None:
        return
    stack = [root]
    while stack:
        curr = stack.pop()
        print(curr.val)
        if curr.right:
            stack.append(curr.right)
        if curr.left:
            stack.append(curr.left)

Space optimized

Time $θ(n)$, Space $θ(h)$

Python

def preOrderSpaceOptimized(root):
    if root == None:
        return
    stack = []
    curr = root
    while stack or curr:
        while curr:
            print(curr.val)
            if curr.right:
                stack.append(curr.right)
            curr = curr.left
        if stack:
            curr = stack.pop()