Level based Representation of a Binary Tree - Load the Tree

This article is part 5 of the series Level based Representation of a Binary Tree

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:

loadByIndex
 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:

load function
 def load( data : List[Union[int,None]] ) -> Node :
     return loadByIndex(data,0)

Now, let's see that it works

run tests
 $ 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

loadByIndex
 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.

loadByIndex
 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.

loadByIndex
 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

run tests
 $ 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?

python quiz