# Symmetric Binary Tree - Use constant memory

If you rememeber, one way to describe a symmetric tree is draw vertical line that start from the root node. If the tree is symmetric, all the nodes with the same distance from this line in the same level are equal.

Using this observation, we need to check for each level:

• The first item of the level is equal to last item, Let's ca
• The second item of the level is equal to second item from end of the level
• The third item of the level is equal to third item from end of the level
• and so on ...

Suppose we have the indexes of first and last items at given level. How can we find the indexes of first and last items of level+1. let's see the pattern (draw and verify)

level items in level first first diff last last diff
0 1 0 x 0 x
1 1 1 +1 2 +2
2 4 3 +2 6 +4
3 8 6 +4 14 +8

Do you see the pattern?

Now, It is easy to write the function

symetricA
`````` def symmetricA(data: List[Union[int, None]]) -> bool:
levelA, levelZ = 0,0
cur_level_items = 1

while levelA < len(data):
aa,zz = levelA, levelZ
while aa <= zz:
if data[aa] != data[zz]:
return False
aa += 1
zz -= 1
levelA += cur_level_items
cur_level_items *= 2
levelZ += cur_level_items
``````

Now, let's run the test

run tests
`````` .E
======================================================================
ERROR: test_symetricA (tests.symetric.TestSymetric)
----------------------------------------------------------------------
Traceback (most recent call last):
File "C:\projects\playground\tests\symetric.py", line 34, in test_symetricA
self.symetric_test(self.assertSymetricA)
File "C:\projects\playground\tests\symetric.py", line 16, in symetric_test
assertFunc([0, 1], False)
File "C:\projects\playground\tests\symetric.py", line 11, in assertSymetricA
assert ( tree.symmetricA(data) == expected )
File "C:\projects\playground\tree\actions.py", line 48, in symmetricA
if data[aa] != data[zz]:
IndexError: list index out of range

----------------------------------------------------------------------
Ran 2 tests in 0.002s
``````

Opps, there is an IndexError. What is wrong?

If you rememeber, the level-based representation of a binary tree allows to emit the last None from the list. Let's fix it.

symetricA
`````` def symmetricA(data: List[Union[int, None]]) -> bool:
cur_level_items = 1
levelA, levelZ = 0,0
while levelA < len(data):
aa,zz = levelA, levelZ
while aa <= zz:
if zz >= len(data):
if data[aa] != None:
return False
elif data[aa] != data[zz]:
return False
aa , zz = aa+1, zz-1
levelA += cur_level_items
cur_level_items *= 2
levelZ += cur_level_items
``````

Now, let's run the test again

run tests
`````` \$ python -m unittest tests.symetric
..
----------------------------------------------------------------------
Ran 2 tests in 0.002s

OK
``````

Now, all tests passed and we successfully solved the 2 parts of the quiz.