Exercise 3 solution

    from collections import deque

    class Node:
        def __init__(self, value, left=None, right=None):
            self.value = value
            self.left = left
            self.right = right

    def inorder_iter(root):
        stack, cur = [], root
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            yield cur.value
            cur = cur.right

    def preorder_iter(root):
        stack = [root] if root else []
        while stack:
            n = stack.pop()
            yield n.value
            if n.right:
                stack.append(n.right)
            if n.left:
                stack.append(n.left)

    def levels(root):
        out, q = [], deque([root] if root else [])
        while q:
            row = []
            for _ in range(len(q)):
                n = q.popleft()
                row.append(n.value)
                if n.left:
                    q.append(n.left)
                if n.right:
                    q.append(n.right)
            out.append(row)
        return out

    t = Node(8, Node(3, Node(1), Node(6)), Node(10, None, Node(14)))
    print(list(inorder_iter(t)))
    print(list(preorder_iter(t)))
    print(levels(t))
    print(levels(None), list(inorder_iter(None)))

    chain = None
    for v in range(5000, 0, -1):
        chain = Node(v, None, chain)       # a 5000-long right-leaning chain
    vals = list(inorder_iter(chain))
    print(len(vals), vals[0], vals[-1])
    print(len(levels(chain)))

Output:
    [1, 3, 6, 8, 10, 14]
    [8, 3, 1, 6, 10, 14]
    [[8], [3, 10], [1, 6, 14]]
    [] []
    5000 1 5000
    5000

The explicit stack replaces the call stack, so depth is limited only by memory.
In-order walks left as far as possible, pops, yields, then moves right.
Pre-order pushes the right child before the left so the left comes off first.
Level order uses a deque (Data Structures in Practice 4) and takes
len(q) items per round, which is exactly one level. The 5000-long chain is
deep enough to defeat a recursive walk (the default limit is about 1000
frames) but all three iterative versions handle it.