 Here's our original solution which is recursive. Try converting it to iterative code, where the function doesn't call itself. ``` def treesEqual(p, q): base case if not p and not q: return True if not p or not q: return False recursion return ( p.val == q.val and treesEqual(p.left, q.left) and treesEqual(p.right, q.right) ) ``` To solve this, we want to create our own Call Stack, which just means storing a `stack` which contains all the inputs that we want to run `treesEqual` on. We could solve

Iterative Trees Equal



-----problem-----

Here's our original solution which is recursive. Try converting it to iterative code, where the function doesn't call itself.

```
def treesEqual(p, q):
    # base case
    if not p and not q: return True
    if not p or not q: return False
    
    # recursion
    return (
        p.val == q.val
        and treesEqual(p.left, q.left)
        and treesEqual(p.right, q.right)
    )
```



-----solution-----

To solve this, we want to create our own Call Stack, which just means storing a `stack` which contains all the inputs that we want to run `treesEqual` on. 

We could solve this problem by visiting every input twice, but it's actually easier to  just return False immediately if we see any trees that are not equal, and return True at the end otherwise.



\answer

\tc $O(n)$

\sc $O(n)$. The stack grows in the same exact way as the recursive solution, so it has the same space complexity.


Iteration

Iterative Trees Equal