Understand recursion
Ahhhh. Okay.

That the issue here is that if the process takes a right branch at node Foo, it needs to store a reference to Foo in the event that it fails to find a child node which is less-than or equal. That reference effectively lives in the stack-calls which occur in inside the calls to the work function. 

There can be an arbitrary number of these calls, so we need an internal, private stack:

def find_val_iterative(parent_node, x):
    right_branch = []
    def _inner(parent_node, x):
        if parent_node is None:
            if right_branch:
                return right_branch.pop().val
            return None
        elif parent_node.val == x:
            return x
        elif parent_node.val &gt; x:
            return _inner(parent_node.left, x)
        else:
            right_branch.append(parent_node)
            return _inner(parent_node.right, x)
    return _inner(parent_node, x)