Check if a binary tree is symmetric in Python

Question

I have solved the following Leetcode problem.

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric.

Link: https://leetcode.com/problems/symmetric-tree/

I have made a simple iterative solution that takes \$O(n)\$ time and \$O(n)\$ space since we have to parse through each node, which is initialized as a class and each class contains the node's values, and pointers to the left and right child of the node. We compare if the node values at each level form a palindromic list (we store all the node values in a running list) or not. Here \$n\$ denotes the number of nodes in the tree. I have assumed the binary tree is complete and any missing node is initialized with a NONE variable. The code terminates when I have reached a level in the tree where each node is a NONE, meaning nothing has to be analyzed at this level, and if an error isn't found in one of the previous nodes (an error is raised when the nodes at each level don't form a palindromic list), we return True.

The code takes a whopping 1500 ms to run on Leetcode and uses around 150 MB of storage! I think about ~200 test cases are run in the background. Running the code on a single tree (of different sizes) makes the code run in about ~30-40ms.

Should I be concerned? Are the other significant ways to optimize the code/approach? I think even if the approach is correct, the implementation may be throwing off the time, and I'm not the most savvy coder. I'm new to learning algorithms and their implementation as well, so I'd appreciate some feedback.

Edit:

Here's my analysis of the run time of the algorithm. Assume the tree is a complete binary tree since each missing node can be thought of a node with a NONE class associated to it. Assume the tree has \$k\$ (starting from level 0) levels and a total of \$n = 2^{k+1} - 1\$ nodes. For example, the tree [1|2,2|3,4,4,3], where a | indicates a level has changed, has \2ドル\$ levels with \$ 2^{3} - 1 = 7 \$ nodes.

The outer while loop terminates when we check the condition of the while loop when we have reached level \$k + 1\$ where this level can be thought as being comprised of all NONE nodes, meaning the tree doesn't extend till this level. So it runs only when the running variable \$l\$ ranges from \0ドル\$ to \$k\$, or a total of \$k + 1\$ times which is \$\Theta ( \lg (n+1)) = \Theta ( \lg n)\$, where \$\lg\$ is log base 2. In the while loop, we have that for each value of \$l\$, the first for loop runs for a total of \2ドル^{l}\$ times since each level has (at most) \2ドル^{l}\$ nodes. The additional for loop runs for only \2ドル\$ times so all in all, for each value of \$l\$ there are \$O(2^{l})\$ iterations. All other operations take constant time, so the running cost of the algorithm is,

$$ \begin{align} O\big(\sum_{l = 0}^{k + 1} 2^{l} \big) &= O\big(\sum_{l = 0}^{\Theta (\lg n)} 2^{l} \big) \\ &= O\big(2^{\Theta (\lg n) + 1 } - 1 \big ) \\ &= O\big(2^{\Theta (\lg n) + 1 } \big) \\ &= O\big(2^{\Theta (\lg n) } \big) \\ &= \Theta (n) \\ &= O(n) \end{align} $$

def isSymmetric(root):
 if root == None:
 return True 
 
 else:
 
 t = [root]
 l = 0
 d = {None:-1}
 
 while d[None] < 2**l:
 
 d[None] = 0
 n = []
 v = []
 
 for node in t:
 
 if node == None:
 
 d[None] = d[None] + 2
 v.append(None)
 v.append(None)
 n.append(None)
 n.append(None)
 
 else: 
 
 for child in [node.left,node.right]:
 
 n.append(child)
 
 if child == None:
 
 d[None] = d[None] + 1
 v.append(None)
 
 else:
 
 v.append(child.val) 
 
 l = l + 1 
 if d[None] == 2**l:
 return True
 
 else:
 
 a = v[0:2**(l-1)]
 b = v[2**(l-1):2**l]
 b.reverse()
 
 
 if a != b:
 return False
 
 t = n

• Mathieu Guindon: Comments are not for extended discussion; this conversation has been moved to chat.

Answer 1

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:

enter image description here

That tree only has 25 nodes, but your solution creates thousands of Nones 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 create millions of Nones.

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

• Peilonrayz: 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.
• Kelly Bundy: @Peilonrayz Quote from their question: "Here n denotes the number of nodes in the tree".
• Peilonrayz: "I have assumed the binary tree is complete and any missing node is initialized with a NONE variable."
• Kelly Bundy: @Peilonrayz And it's nonsensical to assume that.
• Peilonrayz: Certainly is abnormal, but not nonsensical as we can make sense of it.

Answer 2

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 annotations
   import dataclasses
   from typing import Any, Optional
   @dataclasses.dataclass
   class 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 None
   assert 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 same ignoring 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 handle None for both left and right.

   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.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)))
   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 current is_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 if node 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.val
   def 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.val
   def 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.

Answer 3

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 be much 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 the None 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 result
def 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

Draining left and right 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 functions kid1, kid2 and setkid2 (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 result
def leftkid(node):
 return node.left
def rightkid(node):
 return node.right
def setleft(node, kid):
 node.left = kid
def setright(node, kid):
 node.right = kid
def 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, using getattr and setattr, inspired by this 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 result
def 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

Answer 4

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.