Symmetric Tree Check in Python Inspired by This LeetCode Question.

Instead of checking if every layer is symmetric, it instead checks if any aren't. This allows the program to leave early is an early layer fails the test. I'm looking for performance mostly, as I loop through each element in the list, instead of each layer. All feedback is appreciated and considered.

"""
This program determines if a given binary
tree is a mirror of itself

Example:

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3
"""

def is_symmetric(tree: list) -&gt; bool:
    """
    Returns if the passed tree is symmetric

    :param tree: A list representing a binary tree
    """

    interval = 2
    start = 0
    end = 1
    for _ in range(len(tree)):
        # Find next layer
        layer = tree[start:end]

        # Determine if layer isn't mirror
        if layer != list(reversed(layer)):
            return False

        # Setup for next layer
        start = end
        end = (2 ** interval) - 1
        interval += 1

    return True

if __name__ == '__main__':

    assert is_symmetric([1, 2, 2, 3, 4, 4, 3]) # True
    assert not is_symmetric([1, 2, 2, None, 3, None, 3]) # False
Two things:


The function may fail for a tree with an incomplete last layer.  For example:

is_symmetric([1, 2, 2, 3, 4, 3])  returns True, but it should be False.



This can be fixed by checking if layers have the expected length.

if len(layer) != (end - start) or layer != list(reversed(layer)):
        return False



The for loop iterates more times than needed.  The loop only needs to run for each layer in the tree, not for each node.  A tree with n layers has 2**n - 1 nodes. It may not matter for small trees, but a tree with 20 layers has over a million nodes.  Replace the for loop with a while loop:

while start &lt; len(tree):
...

Okay, three things.  interval isn't needed.  Use:

end = 2 * end + 1



The revised routine:

def is_symmetric(tree: list) -&gt; bool:
    """
    Returns if the passed tree is symmetric

    :param tree: A list representing a binary tree
    """

    start = 0
    end = 1

    while start &lt; len(tree):
        # Find next layer
        layer = tree[start:end]

        # Determine if layer isn't mirror
        if len(layer) != (end - start) or layer != list(reversed(layer)):
            return False

        # Setup for next layer
        start = end
        end = 2 * end  + 1

    return True


if __name__ == '__main__':
    tests = [
        ([1], True),
        ([1, 2, 2, 3, 4, 4, 3], True),
        ([1, 2, 2, None, 3, None, 3], False),
        ([1, 2, 2, 3, 4, 3], False)
        ]

    for n, (test, answer) in enumerate(tests):
        result = is_symmetric(test)
        print(f"Test {n} {'Pass' if answer==result else 'FAIL'}: is_symetric({test})")