Depth First Search

• in-order: left -> root (parent P) -> right
• pre-order: root -> left -> right
• post-order: left -> right -> root

tip

Prefer in-order or pre-order because they are tail recursive

In-order (LPR)

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

Python

def inOrder(root):
    if not root:
        inOrder(root.left)
        print(root.val)
        inOrder(root.right)

Pre-order (PLR)

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

Python

def preOrder(root):
    if not root:
        print(root.val)
        preOrder(root.left)
        preOrder(root.right)

Post-order (LRP)

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

Python

def postOrder(root):
    if not root:
        postOrder(root.left)
        postOrder(root.right)
        print(root.val)

Height of tree

• 1st convention: number of nodes on longest path (h1)
• 2nd convention: number of edges on longest path (h2) Time: $θ(n)$, Space: $θ(h)$

Python

def height(root): # h1
    if root == None:
        return 0 # replace with -1 for h2
    lh = height(root.left)
    rh = height(root.right)
    return 1 + max(lh, rh)