Iteration

Iterative Trees Equal

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)
    )

First Few Test Cases:

treesEqual(TreeNode.of([7]), TreeNode.of([7]))
# True

treesEqual(TreeNode.of([7]), TreeNode.of([6]))
# False

treesEqual(TreeNode.of([5, 2]), TreeNode.of([5, 2]))
# True

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.

def treesEqual(p, q):
    # at first, we just want to call `treesEqual` on the two roots.
    stack = [(p, q)]

    while stack:
        # take nodes off the stack and call treesEqual() on them
        P, Q = stack.pop()

        if not P and not Q: continue     # both nodes are null
        if not P or  not Q: return False # only 1 node is null

        if P.val != Q.val:
            return False
        
        stack.append((P.right, Q.right))
        stack.append((P.left, Q.left))

    # if we made it through all the calls without returning False, then the trees are equal
    return True

Time Complexity $O(n)$

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

Mark as Completed:

Submits:

treesEqual

Imports:

TreeNode

Test your code to get an output here!

treesEqual(

)

Test your code to get an output here!