Check whether a binary tree is symmetric

Question

I implemented a recursive solution that compares the left and right subtree in mirrored fashion. It works for my test cases, but I would like to know if there are any best practices that would make it cleaner or faster.

class TreeNode:
 def __init__(self, val=0, left=None, right=None):
 self.val = val
 self.right = right
 self.left = left #this is just the begining of the data, left and right pointer basic
class Solution:
 def isSymmetric(self, root):
 if root is None: #1st function if both are none
 return True
 return self.comparar(root.left, root.right) #dame func comparar
 def comparar(self, nodoA, nodoB): #we add 2 more parameteer as nodos to go tru
 if nodoA is None and nodoB is None:
 return True
 if nodoA is None or nodoB is None:
 return False
 if nodoA.val != nodoB.val:
 return False
 return self.comparar(nodoA.left, nodoB.right) and self.comparar(nodoA.right, nodoB.left)
if __name__ == "__main__":
 root = TreeNode(10)
 sol = Solution()
 print(sol.isSymmetric(root))

As I said, I want to know whether there is another way to approach the algorithm. Or perhaps if an iterative solution might be faster - last time someone told me that recursive algorithms are better, but I don't know whether that is true for this code.

Any suggestions to improve structure, clarity or performance will be appreciated.

• Reinderien: Have you checked whether something like NetworkX supports this out of the box?
• Martin R: Is this a problem from some coding/contest platform? If yes, can you add a link to the original question? Perhaps this leetcode.com/problems/symmetric-tree ?
• Jared McCarthy: I hadnt thought of NetworkX for this, thanks for pointing it out @Reinderien i will check if it has something similar built in.
• Jared McCarthy: @MartinR yes it is from leetcode actually, last time i asked on stackflow about a leetcode question i got closed btw, so fo that reason i didnt add the link for context, but yes i was looking for a dif way to do this because it was kinda complicate to completed it.
• Kelly Bundy: @JaredMcCarthy It didn't get closed because of LeetCode.

Answer 1

I note that this algorithm determines tests whether the tree's structure is symmetric, as well as the content. I haven't seen the problem specification, so have to assume that that is a requirement - it's probably worth adding suitable doc-comments that make the assumption explicit to readers.

The class Solution is too generically named, and isn't necessary anyway - just write isSymmetric() and comparar() as free functions. Unlike Java, Python doesn't require all functionality to be part of a class.

Otherwise, the code is clear and straightforward even though it's not entirely in English. There's no need to modify it unless your trees are so deep that recursion causes a stack overflow. I note that each node is visited just once, which is clearly the least amount of comparison that is necessary, so there's no scope to increase performance.

The test case provided doesn't exercise the code very well. A tree with a single node will always be symmetric; you need test cases with multiple levels, both symmetric and asymmetric. It's especially important to have good tests that work with the obvious simple function before you do any refactoring for performance or scalability.

• Martin R: class Solution is part of the Python submission template on some coding platforms like LeetCode: leetcode.com/problems/symmetric-tree
• Peter Cordes: @MartinR: Good to know, but I hope you agree it's still bad coding style for any case where you aren't required to do that. If the OP wrote it for something like LeetCode and wanted to repost it here unchanged, they could have added a comment explaining that ugly class name. Or just taken it out to create more polished code for people to review.
• Jared McCarthy: Thank you for the feedback, amd yes youre right about the Solution class, I kept it because of the LeetCode template, but I see how outside of that context it makes sense to remove it. i will also improve my test cases to cover more than just the trivial ones. Appreciate the clarity on recursion limits and performance too.
• Toby Speight: Thanks for clarification @Jared. If you post similar Solution classes in other reviews, you can help reviewers by explaining that's a constraint you were given rather than something you chose. One possible approach could be if __name__ == '__main__': - normal code - else: class Solution so that your tests exercise the functions and the class is just a thin wrapper.

Answer 2

communicating with humans

Something that can take a long time for junior devs to realize is that coding is primarily about communicating a technical idea to colleagues.

programs must be written for people to read, and only incidentally for machines to execute.

--SICP

At first you loop through an edit-debug cycle with the machine, but later you'll find that most of your interactions are with codebases shared among colleagues, where we're trying to herd all the cats in a similar direction. Being able to read and understand someone's code becomes paramount there.

Crucially, that "someone else" reading the code will be you in a few months time. You will have moved on, become a slightly different person, with many algorithm details forgotten. Be kind to the future you, and write your source code with that person in mind.

natural language

This is a Spanish - English project, with three kinds of material.

1. identifiers in code
2. # comments and """docstrings"""
3. UX interactions with end user

Item (3.) is always a hard requirement dictated by who the end users are. Here it is empty set, as no output is printed to the console.

Item (2.) could go either way, since strictly speaking comments are optional. To the extent that current and future technical staff are comfortable with English, standard advice is to stick with the lingua franca of English. As a project evolves and its code is more widely shared, this tends to reduce the code's support costs. Since sometimes "comments lie!" and will distract a maintenance engineer, it is important for identifier words and comment words to match one another.

For item (1.), I recommend you lean more heavily in the "English only" direction. In the workplace the language skills of your colleagues could strongly influence this choice. But here, you're explicitly posting the code to a strictly English site, so that imposes a requirement from the get go. I have seen Code Review contributors try to do a one-time translation for purposes of posting, but that carries attendant risks of making typos and copy-n-paste errors when transforming the "released" codebase into the "posted" codebase.

consistency

I found that # dame func comparar was a perfectly good comment. But its language doesn't match that of the other comments, which is a little jarring. Consider adopting a single natural language across all comments.

Additionally, the comments mostly seemed pretty obvious and could be safely deleted, as the corresponding code is self-explanatory. We use code to explain how we're computing something, and comments to explain why we chose to do it a certain way.

There's a pair of functions in the Solution class, and each draws its name from a different language.

I found this a bit jarring:

...(nodoA.left, nodoB.right) ...

Wouldn't nodoB.derecha be a more natural way to express that notion?

When mixing different modules and libraries, often they will be composed of a critical mass of English code, which tends to influence the choice of language for a new codebase you create. We wish to see smooth integration when we compose many packages.

computer language

Python is not javascript.

The indenting matters, but also the snake_case and CapitalizedClassNames matter; they affect how quickly we can read and understand code.

I recommend you adopt identifiers of is_symmetric(), compare(), and node_b.

type annotation

Consider insisting that the tree stores only numeric values, e.g.
...(self, val: float = 0, ...
(Or int, if you prefer.)

dataclass

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

This is a perfectly nice setup, it's bog standard. But a bit tediously boring.

Consider relying on a standard library module that ships with modern interpreters:

from dataclasses import dataclass
@dataclass
class TreeNode:
 val: float
 left: "TreeNode"
 right: "TreeNode"

• Martin R: I suspect that OP is trying to solve leetcode.com/problems/symmetric-tree/description, in that case the class TreeNode is already defined in the LeetCode environment.
• Jared McCarthy: i see what you mean about code being for humans to read first, mixing english and spanish in identifiers and comments was not helpful and now i think about it. Also the note about snake_case and class naming makes sense, it really helps with readability. And the dataclass suggestion is interesting, i hadnt thought about using that here but it looks cleaner.
• Jared McCarthy: Yes @MartinR, it was from the LeetCode symmetric tree problem. TreeNode was already defined there, i just copied the structure over for context.

Answer 3

In addition to the previous answer by @Toby Speight, here are some general coding style suggestions.

Documentation

The PEP 8 style guide recommends adding docstrings for classes and functions.

You could add a docstring to the top of the code to summarize its purpose, such as:

"""
Check whether a binary tree is symmetric
Add more details here.
"""

Comments

This comment in the isSymmetric function is not very helpful:

if root is None: #1st function if both are none

I don't understand how it is supposed to describe the code. You should either delete it or change it to be more descriptive.

This comment can be deleted:

return self.comparar(root.left, root.right) #dame func comparar

Again, it does not really describe the code.
It is cryptic, uses an abbreviation and is multi-lingual.

This comment should be replaced with a docstring:

def comparar(self, nodoA, nodoB): #we add 2 more parameteer as nodos to go tru

Naming

The PEP 8 style guide recommends snake_case for function and variable names.

isSymmetric would be is_symmetric.

nodoA would be nodo_a (or node_a), etc.

• Jared McCarthy: Thanks for pointing that out, i see now that some of my comments werent clear and mixed languages, so i will fix that and add proper docstrings instead. i will also rename the functions and variables to follow snake_case as PEP 8 suggests.

Answer 4

Re. avoidable effort: nesting the None checks avoids one or two of three comparisons for nodes with two children:

def _mirrored(a, b):
 """ Are binary trees rooted in a and b each other's mirror image?
 Return: True if mirror images, else False
 """
 if a is None or b is None:
 return a is b
 if a.val != b.val:
 return False
 return _mirrored(a.left, b.right) and _mirrored(a.right, b.left)

I think the above, doing three comparisons where None is b and b is not a, more readable than below two comparison variant

 if a is None:
 return a is b
 if b is None:
 return False

Any runtime differences should be leveled by "really compiling" (PyPy, mypyc, Numba, ...).

Answer 5

Your recursive solution to this is a reasonable approach for a recursive data structure. There is an opportunity to abstract getting mirrored nodes out from the process of checking for their equality by using iterators.

def iter_mirrored_pairs(left, right):
 yield (left, right)
 if left is None or right is None and left is right:
 return
 yield from iter_mirrored_pairs(right.left, left.right)
 yield from iter_mirrored_pairs(left.left, right.right)

Now, for our solution we only need to check if all of the mirrored pairs are equal.

def vals_equal(left, right):
 if left is None or right is None:
 return left is right
 
 return left.val == right.val
class Solution:
 def isSymmetric(self, root):
 if root is None: 
 return True
 return all(
 vals_equal(l, r) 
 for l, r in iter_mirrored_pairs(root.left, root.right)
 )

This abstraction might be leveraged to check for mirrored structure of the binary tree without worrying about the values without having to rewrite the recursive logic.

• CiaPan: Is the part and left is right necessary? You want to skip recurring on None objects, and that seems already tested by the preceding alternative.
• Chris: Feel free to suggest a replacement. The nice thing about abstracting it away is that we ensure improvements in this one function will improve any calling code.
• CiaPan: No, I won't, because I do not understand that part. If I did, I would have started with a fix suggestion, but I don't, hence I ask for explanation.
• Kelly Bundy: @CiaPan Yeah that part is pointless, it can never evaluate as true.
• Kelly Bundy: @Chris Still inefficient. Tried with a symmetric tree of 1801 nodes and depth 900, your solution took about 40 times as long as the OP's original. This should really only take O(n) time like theirs, not O(n^2) like yours (where n is the number of nodes).