-1

I have a working recursive solution to check if a binary tree is symmetric. The code works correctly for my test cases, but I'm concerned about potential stack overflow with deep trees since Python has a default recursion limit.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isSymmetric(self, root):
        if root is None:
            return True
        return self.compare(root.left, root.right)
    
    def compare(self, nodeA, nodeB):
        if nodeA is None and nodeB is None:
            return True
        if nodeA is None or nodeB is None:
            return False
        if nodeA.val != nodeB.val:
            return False
        return (self.compare(nodeA.left, nodeB.right) and 
                self.compare(nodeA.right, nodeB.left))

These are the test cases that works:

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.right.right = TreeNode(3)

sol = Solution()
print(sol.isSymmetric(root))  # Output: True

The problem is when testing with a tree that has depth > 1000 nodes, I get:

RecursionError: maximum recursion depth exceeded in comparison

I understand this is O(n) time complexity which is optimal, but the recursive approach uses O(h) space on the call stack where h is tree height.

How can I convert this recursive solution to an iterative one using an explicit stack or queue to avoid Python's recursion limit while maintaining the same comparison logic (mirrored left-right traversal)?

I've tried using a single stack but I'm not sure how to properly track both subtrees simultaneously for the mirrored comparison.

def isSymmetric(self, root):
    if not root:
        return True
    stack = [(root.left, root.right)]

    # Not sure how to proceed from here to compare nodes correctly

What's the correct way to manage the stack to compare pairs of nodes in mirror order?

Improve this question
7
  • 1
    As your code works, there is no problem here. It seems you are asking for a code review. You could check out the guidelines of Code Review and post there accordingly. In terms of time complexity, this is O(n), and that is optimal. Commented Sep 20 at 6:45
  • As user @trincot points out, this is not the place for code reviews. But recursive solutions certainly incur some overhead, in both speed and space on the stack, which also limits how large the tree you can compare will be in specific ways. The best solution generally depends on where you intend to apply it. If your trees are relatively small and you want to keep your code clean and simple, the current solution is fine. If you must have the best performance, writing it in pure Python may not be ideal in the first place. If you run into specific issues optimising, come back to ask about those. Commented Sep 20 at 7:03
  • @Grismar you mentioned recursion can hit stack limits for large trees, so how would an iterative aproach with stack may help reduce stack usage while still checking tree symmetry? Commented Sep 20 at 7:11
  • One best practice is to write code in English, especially when you post it on an English-speaking site. Commented Sep 20 at 8:05
  • @JaredMcCarthy user trincot has provided an example below, but more generally any recursive solution can be implemented iteratively and although there is still a cost in time and space for the algorithm, it puts you in control of the implementation. Recursion is often the better solution for readable and maintainable code though. Again: you should point out the specific problem you need to solve, there's no universally "better" solution. Your question as it stands only serves to start opinionated debate. Commented Sep 20 at 21:29

1 Answer 1

Reset to default
2

In terms of time complexity this algorithm is optimal.

Note that if the input is symmetrical, the recursion depth will be equal to the height of the given binary tree. If that height is large, you may bump into a stack limit. An alternative approach is to work with an explicit stack, like this:

class Solution:
    def isSymmetric(self, root):
        if root:
            stack = [(root.left, root.right)]
            while stack:
                a, b = stack.pop()
                while a or b: # while the current pair has at least one node
                    # if there is a difference, the trees are not symmetrical
                    if not a or not b or a.val != b.val:
                        return False
                    # put one child pair on the stack for later inspection
                    stack.append((a.left, b.right))
                    # take the other child pair as current pair, and repeat
                    a = a.right
                    b = b.left
        # all relevant pairs were compared and found equal
        return True

This explicit stack will have pairs of nodes, where one pair consists of a node from the left tree and one from the right tree, which still need to be compared for symmetry. When the nodes in such a pair have the same value, two "child" pairs are considered: one is put on the stack for later inspection, and the other pair becomes the current pair. That way all relevant pairs can be visited and compared.

Space complexity

Even though this iterative version will not be limited by the call stack limit, it could still use O(𝑛) auxiliary memory in the worst case, like when the input tree is symmetric and has all its nodes on two long branches forming the shape of a tent:

             /\
            /  \
           /    \
          ..    ..
         /        \

It is a pity that the caller of this function can easily design a tree that realises this worst case memory usage. To avoid that, you could randomly choose which pair will be pushed on the stack, and which one will be used as the current pair. That way the caller cannot intentionally provide a worst-case tree in terms of memory complexity.

import random

class Solution:
    def isSymmetric(self, root):
        if root:
            stack = [(root.left, root.right)]
            while stack:
                a, b = stack.pop()
                while a or b:
                    if not a or not b or a.val != b.val:
                        return False
                    # randomly decide which pair will be put on the stack
                    if random.randrange(2):
                        a, b = b, a
                    stack.append((a.left, b.right))
                    a = a.right
                    b = b.left
        return True
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

This is the kind of answer I was looking for, It shows how to do the same check iteratively with less code, and it makes the trade off with recursion very clear. really appreciate @trincot, i alway write multiple ways to solve algorithms and have irt more clear.
btw this was not easy to understand either, but is almsot the same except this time it is only iterating with one class < def.
Malicious me can call with a.left is a and b.right is b.
Yes, but the question was about a binary tree.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.