So, your task is to write the load function. Can you think about how to do it?
Suppose, you are given an index and level based representation of a binary tree. can you tell, what is the index of its left child and what is the index of its right index?
Let's see some examples :
Node index | Left child index | Right child index |
---|---|---|
0 | 1 | 2 |
1 | 3 | 4 |
1 | 5 | 6 |
3 | 7 | 8 |
4 | 9 | 10 |
Do you see the pattern? It is easy to see:
Node index | Left child index | Right child index |
---|---|---|
k | 2*k+1 | 2*k+2 |
Now that we regonize the pattern, we can write:
def loadByIndex(data: List[Union[int, None]], kk: int):
# if the node does not exist in the list
if kk >= len(data):
return None
# find the value stored in current Node
value = data[kk]
# if the item is None, there is no node at this position
if value is None:
return None
# load the left child subtree
left = loadByIndex(data, kk * 2 + 1)
# load the right child subtree
right = loadByIndex(data, kk * 2 + 2)
# create the new tree
return Node(value, left, right)
So, using this function we can easily load the tree:
def load( data : List[Union[int,None]] ) -> Node :
return loadByIndex(data,0)
Now, let's see that it works
$ python -m unittest tests.load
.....
----------------------------------------------------------------------
Ran 5 tests in 0.002s
OK
Yes, we solved the first task. However, can we write a better code
We write a helper function that is used only in the load function, let's move this function as inner function of load
def load(data: List[Union[int, None]])
def loadByIndex(data: List[Union[int, None]], kk: int):
# if the node does not exist in the list
if kk >= len(data):
return None
# find the value stored in current Node
value = data[kk]
# if the item is None, there is no node at this position
if value is None:
return None
# load the left child subtree
left = loadByIndex(data, kk * 2 + 1)
# load the right child subtree
right = loadByIndex(data, kk * 2 + 2)
# create the new tree
return Node(value, left, right)
return loadByIndex(data,0)
It seems the code is verbose. Let's fix it. first, there is no need to move data to the function as it is available by defualt from the outer function.
def load(data: List[Union[int, None]]):
def loadByIndex(kk: int):
# if the node does not exist in the list
if kk >= len(data):
return None
# find the value stored in current Node
value = data[kk]
# if the item is None, there is no node at this position
if value is None:
return None
# load the left child subtree
left = loadByIndex(kk * 2 + 1)
# load the right child subtree
right = loadByIndex(kk * 2 + 2)
# create the new tree
return Node(value, left, right)
return loadByIndex(0)
Now, that we have tests, we can be confident in refactoring the code.
def load(data: List[Union[int, None]]):
def loadByIndex(kk: int):
# if the node does not exist in the list
if kk >= len(data) or data[kk] is None:
return None
# load Node, the left node located kk*2+1 and right node located at kk*2+2
return Node(data[kk], loadByIndex(kk * 2 + 1), loadByIndex(kk * 2 + 2) )
Let's run the unittest again, and check that new changes we made in the code still works
$ python -m unittest tests.load
.....
----------------------------------------------------------------------
Ran 5 tests in 0.002s
OK
Now, can you write the tests for the dump functions and implement it?