Symmetric Binary Tree - Use constant memory

This article is part 5 of the series Symmetric Binary Tree

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.