Your solution isn't\$O(n)\$ but\$O(2^n)\$. Your assumption that the tree is complete and thus your analysis is incorrect. Already LeetCode's second example tree isn't complete. And consider this tree:

That tree only has 25 nodes, but your solution createsthousands ofNones for subtrees that aren't there. (That is, your actual code presumably does that, not the one that you posted here and refuse to fix.) If I made it ten levels deeper (45 nodes total), you'd createmillions ofNones.

The above tree btw can be denoted at LeetCode by this:

[1,1,1,null,1,1,null,null,1,1,null,null,1,1,null,null,1,1,null,       null,1,1,null,null,1,1,null,null,1,1,null,null,1,1,null,       null,1,1,null,null,1,1,null,null,1,1,null]

Just another solution, in which I tuplify the tree and then compare it to a mirrored version of it. It's recursive, which for binary tree problems is often simpler:

    def isSymmetric(self, root: TreeNode) -> bool:        def t(r):            return r and (r.val, t(r.left), t(r.right))        def m(r):            return r and (r[0], m(r[2]), m(r[1]))        r = t(root)        return r == m(r)

Got accepted in 16 ms. Note that the abbreviated function/variable names are bad in real life. But for a contest it can save time, so I kinda wanted to show that, as writing speed has been mentioned in comments elsewhere. Similarly, I waste space on a mirrored copy because that way I pretty much don't have to think, again saving writing time :-)

• \$\begingroup\$Isn't this discrepancy because you have different definitions of \$n\$? The OP has defined \$n\$ to be a complete tree where you have defined \$n\$ to be the amount of nodes in the tree. It's not really nonsensical to have different definitions just as long as you're up-front about them which IIRC the OP was.\$\endgroup\$

  Peilonrayz

  – Peilonrayz♦

  2020-09-27 17:04:14 +00:00

  CommentedSep 27, 2020 at 17:04
• \$\begingroup\$@Peilonrayz Quote from their question: "Here n denotes the number of nodes in the tree".\$\endgroup\$

  Kelly Bundy

  – Kelly Bundy

  2020-09-27 17:06:14 +00:00

  CommentedSep 27, 2020 at 17:06
• \$\begingroup\$"I have assumed the binary tree is complete and any missing node is initialized with a NONE variable."\$\endgroup\$

  Peilonrayz

  – Peilonrayz♦

  2020-09-27 17:06:39 +00:00

  CommentedSep 27, 2020 at 17:06
• \$\begingroup\$@Peilonrayz And it's nonsensical to assume that.\$\endgroup\$

  Kelly Bundy

  – Kelly Bundy

  2020-09-27 17:06:57 +00:00

  CommentedSep 27, 2020 at 17:06
• 3
  \$\begingroup\$Certainly is abnormal, but not nonsensical as we can make sense of it.\$\endgroup\$

  Peilonrayz

  – Peilonrayz♦

  2020-09-27 17:08:20 +00:00

  CommentedSep 27, 2020 at 17:08

It would also be easier if we follow TDD -Test Driven Development.

1. We build the boiler plate that LeetCode is building for you.

   from __future__ import annotationsimport dataclassesfrom typing import Any, Optional@dataclasses.dataclassclass Node:    val: Any    left: Optional[Node] = None    right: Optional[Node] = None

2. We get a tree with only one node working.From this we can expand on the tests and code to get more working.

   This is simple we just check if both left and right are None.

   def is_symmetric(node):    return node.left is None and node.right is Noneassert is_symmetric(Node(None))

3. We get a tree with 3 nodes working.

   The simplest way to do this is to just check if left and right's value are the sameignoring if either are None.

   def is_symmetric(node):    return (        (node.left is None and node.right is None)        or (node.left.val == node.right.val)    )assert is_symmetric(Node(None))assert is_symmetric(Node(None, Node(1), Node(1)))assert not is_symmetric(Node(None, Node(1), Node(2)))

4. We get a tree of size 1, 2 and 3 working.

   This makes the code a little more complicated as we now have to handleNone for bothleft andright.

   def is_symmetric(node):    if node.left is None:        return node.right is None    if node.right is None:        return False    return node.left.val == node.right.valassert is_symmetric(Node(None))assert is_symmetric(Node(None, Node(1), Node(1)))assert not is_symmetric(Node(None, Node(1), Node(2)))assert not is_symmetric(Node(None, left=Node(1)))assert not is_symmetric(Node(None, right=Node(1)))

5. To get a easier to understand stepping stone we can temporarally solve a different problem.Rather than checking if it's a mirror arround the root we just check the mirror around each node.

   Note: This is only to make this step easier to digest.

   Since we already have a function to check if a node is symmetric we can just call that to check if each of left and right are symmetric. This is called recursion.

   To return True the currentis_symmetric needs to be true, and both the left and right have to be symmetric.

   To make the code a little easier to read we can:

   1. Move the current code into another function.
   2. Add a condition to return True ifnode is None.

   def _is_symmetric(node):    if node.left is None:        return node.right is None    if node.right is None:        return False    return node.left.val == node.right.valdef is_symmetric(node):    if node is None:        return True    return _is_symmetric(node) and is_symmetric(node.left) and is_symmetric(node.right)assert is_symmetric(Node(None))assert is_symmetric(Node(None, Node(1), Node(1)))assert not is_symmetric(Node(None, Node(1), Node(2)))assert not is_symmetric(Node(None, left=Node(1)))assert not is_symmetric(Node(None, right=Node(1)))assert is_symmetric(None)assert is_symmetric(Node(    None,    Node(1, Node(2), Node(2)),    Node(1, Node(3), Node(3)),))assert not is_symmetric(Node(    None,    Node(1, Node(2), Node(1)),    Node(1, Node(3), Node(3)),))

6. We can now go back to solving the original problem. By swapping two grand-child nodes we can change the above to work down the middle of the tree.

   def _is_symmetric(node):    if node.left is None:        return node.right is None    if node.right is None:        return False    return node.left.val == node.right.valdef is_symmetric(node):    if node is None:        return True    if not _is_symmetric(node):        return False    if node.left is not None:        (node.left.left, node.right.left) = (node.right.left, node.left.left)    return is_symmetric(node.left) and is_symmetric(node.right)assert is_symmetric(Node(None))assert is_symmetric(Node(None, Node(1), Node(1)))assert not is_symmetric(Node(None, Node(1), Node(2)))assert not is_symmetric(Node(None, left=Node(1)))assert not is_symmetric(Node(None, right=Node(1)))assert is_symmetric(None)assert is_symmetric(Node(    None,    Node(1, Node(2), Node(3)),    Node(1, Node(3), Node(2)),))assert not is_symmetric(Node(    None,    Node(1, Node(2), Node(3)),    Node(1, Node(3), Node(1)),))

This runs in\$O(n)\$ time and\$O(d)\$ space, where\$d\$ is the depth of the tree. This is because we make\$d\$ stack frames because we have used recursion. On a complete tree\$d\$ is\$\log n\$ but can be as bad as\$n\$ on a tree that is more line like.

O(1) space, O(n) time

As kinda pointed out already, your lists of nodes/values of the current level are up to\$O(2^n)\$ large. So your large memory usage of 150 MB is no wonder. It could easily bemuch more. LeetCode must have only very shallow trees (Yeah just checked, max height is only 22. Sigh). Here's somewhat the other extreme, taking only O(1) extra space. And it can handle any tree height, unlike recursive solutions which would at some point exceed the recursion limit and crash.

I'm using Morris traversal for a preorder left-to-right traversal of the root's left subtree and a right-to-left one of the right subtree. I yield not just the node values but also theNone references. That provides not just the values but also the structure of the two subtrees, so then I just need to compare the left traversal with the right traversal one by one.

At LeetCode it still takes about 14.3 MB, as LeetCode doesn't isolate the solution's memory usage but includes the Python/judge overhead. I also took a solution from the memory distribution graph that had a very low memory usage (13628 kB) and resubmitted it. It took 14.3 MB now as well. So as with times, LeetCode isn't stable and accurate with memory, and the baseline (minimum) seems to be about 14.3 MB right now.

class Solution:    def isSymmetric(self, root: TreeNode) -> bool:        if not root:            return True        left = preorder_left_right(root.left)        right = preorder_right_left(root.right)        result = all(map(operator.eq, left, right))        for _ in left: pass        for _ in right: pass        return resultdef preorder_left_right(root):    while root:        if not root.left:            yield root.val            yield None            root = root.right            continue        prev = root.left        while prev.right and prev.right is not root:            prev = prev.right        if not prev.right:            yield root.val            prev.right = root            root = root.left        else:            yield None            prev.right = None            root = root.right    yield None    def preorder_right_left(root):    while root:        if not root.right:            yield root.val            yield None            root = root.left            continue        prev = root.right        while prev.left and prev.left is not root:            prev = prev.left        if not prev.left:            yield root.val            prev.left = root            root = root.right        else:            yield None            prev.left = None            root = root.left    yield None

Drainingleft andright isn't necessary at LeetCode to get accepted,return all(map(operator.eq, left, right)) works there as well. But I do it to finish the Morris traversals and thus restore the trees to their original states.

I considered replacing the two traversal functions with one that takes functionskid1,kid2 andsetkid2 (getting/setting the left or right kid of a node) to remove the code duplication, but I think it's clearer the way it is. Edit: Oh well, actually did it now:

class Solution:    def isSymmetric(self, root: TreeNode) -> bool:        if not root:            return True        left = preorder(root.left, leftkid, rightkid, setright)        right = preorder(root.right, rightkid, leftkid, setleft)        result = all(map(operator.eq, left, right))        for _ in left: pass        for _ in right: pass        return resultdef leftkid(node):    return node.leftdef rightkid(node):    return node.rightdef setleft(node, kid):    node.left = kiddef setright(node, kid):    node.right = kiddef preorder(root, kid1, kid2, setkid2):    while root:        if not kid1(root):            yield root.val            yield None            root = kid2(root)            continue        prev = kid1(root)        while kid2(prev) and kid2(prev) is not root:            prev = kid2(prev)        if not kid2(prev):            yield root.val            setkid2(prev, root)            root = kid1(root)        else:            yield None            setkid2(prev, None)            root = kid2(root)    yield None

Yet another version, usinggetattr andsetattr, inspired bythis attempt:

class Solution:    def isSymmetric(self, root: TreeNode) -> bool:        if not root:            return True        left = preorder(root.left, 'left', 'right')        right = preorder(root.right, 'right', 'left')        result = all(map(operator.eq, left, right))        for _ in left: pass        for _ in right: pass        return resultdef preorder(root, kid1, kid2):    get, set = getattr, setattr    while root:        if not get(root, kid1):            yield root.val            yield None            root = get(root, kid2)            continue        prev = get(root, kid1)        while get(prev, kid2) and get(prev, kid2) is not root:            prev = get(prev, kid2)        if not get(prev, kid2):            yield root.val            set(prev, kid2, root)            root = get(root, kid1)        else:            yield None            set(prev, kid2, None)            root = get(root, kid2)    yield None

Thank you for the suggestions everyone. I was able to figure out the lapse in my initial judgement, and I was able to think of a solution that works, and I was able to implement it as well (after some hiccups and minor modifications along the way). Here's what I got:

def isSymmetric(self,root):    if root == None:        return True             else:            t = [root]        l = 0            while len(t) > 0:                    l = l + 1            v = []            n = []                        for node in t:                                if node.left != None:                                            n.append(node.left)                    v.append(node.left.val)                                    else:                                        v.append(None)                                      if node.right != None:                                        n.append(node.right)                    v.append(node.right.val)                                    else:                                        v.append(None)                         a = v[::-1]                                if a != v:                return False                            t = n                return True

It now runs in around 26ms, which is faster than 96.67% of submissions, but it still uses about 13 MB of storage, which is less than 5.09% of submissions. I can live with that since I'm probably not the slickest of coders, but I'll try and see if I can optimize and/or learn new ways for better implementation.

• python
• programming-challenge
• tree
• palindrome