# Level Based Representation Of Binary Tree [With 2 Simple Quiz]

We say that a level-based representation of a binary tree (or list representation of a binary tree) is a list of items. Each item in this list represents a node. The value can be an integer or None. If the value is an integer, it is the data stored in the node. However, the value can be None – this special case means that the node at the given position does not exist.

The order is based on the level of the node. In other words :

• the first node is the root (all the nodes at level 0)
• then its 2 children (all the nodes at level 1)
• then their 4 children (all the nodes at level 2)
• and so on.

Each level is ordered from left to right. so:

• The item at index 0 is the root
• The item at index 1 is the left child of the root
• The item at index 2 is the right child of the root
• The item at index 3 is the left child of the left child of the root
• The item at index 4 is the right child of the left child of the root
• and so on

A level-based representation of a binary tree allows emitting the last items of the list if their value is None. In other words, To conclude whether a node at the given position does not exist in a level-based representation of a binary tree:

• Check that item is not on the list
• Otherwise, check that the value of the item is None.

## Samples of level-based representation of Binary Tree

Let’s see some samples. In the following graphs:

• Each node is represented by a grey circle.
• The number inside the circle represents the value stored in the node.
• The red circles are nodes that should exist in the full binary tree but do not exist in this tree

## Quizs For List Representation Of Binary Tree

Given the following Node class:

###### Node in binary tree
`````` class Node:
def __init__(self,data,left,right):
self.data  = data
self.left  = left
self.right = right``````

### Part 1 – build tree

Write a function that takes a level-based representation of a binary tree and generate the root node of a binary tree

``````def load(repr : List[Union[int,None]]) -> Node:
pass``````

### Part 2 – dump tree

Write a function that takes a the root node of a binary tree and return its level-based representation

###### Dump tree to list
``````def dump(tree : Node) -> List[Union[int,None]]:
pass``````

## Design The tree Package with load and dump

So, Let’s solve the quiz.

As we start the project let’s think about the usage of the functions. We want all related functions to reside in the tree package. The user of the package should be able to import the package and start using the dump and load functions

###### Sample of using the tree package
``````>>> import tree
...
>>> root.right = Node(2,None,None)
...
>>> tree.dump(tree)
[0,None,2]``````

To do so follow the following steps :

First, let’s create the “tree” under the project root directory. Now create the “tree/node.py” and define the Node class.

###### tree/node.py
``````class Node:
def __init__(self,data : int ,left : 'Node' , right : 'Node'):
self.data  = data
self.left  = left
self.right = right``````

Now, create the “tree/actions.py” and create the load and dump stubs.

###### tree/actions.py
``````from typing import List,Union
from .node import Node

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

def dump( tree : Node ) -> List[Union[int,None]] :
return None``````

### Making directory to a package

Now, let’s convert the “tree” directory to a package, by creating “tree/__init__.py”. This file will expose the the Node class and the actions to the outside world.

###### The tree/__init__.py
``````from .node import Node
from .actions import dump``````

Let’s see the directory structure so far:

###### Directory structure so far
``````project
├── tree
├── __init__.py
├── node.py
├── actions.py``````

## Writing Tests with unittest

Let’s add some tests load function. We will use the builtin unittest package. Follow the following steps:

Create a new package tests. In other words, create a new directory named tests alongside the tree package and also create a new empty file __init__.py inside this directory

###### Directory structure so far
``````project
├── tree
├── __init__.py
├── node.py
├── actions.py
├── tests
├── __init__.py``````

Now, Create a module load.py which contains our test case. we also import the load function, we want to test in this test case

``````import unittest

...``````

### Writing the assert functions

In the tests, we should check whether the actual nodes loaded by the load function are equal to the expected nodes.

What should we test?

First, We need to test that the data stored in the actual is equal to the data stored in the expected node.

We also need to test whether the actual node has the same children as the expected node. There are four cases for that:

• The node has both left and right children.
• The node has a left child but does not have a right child.
• The node has a right child but does not have a left child.
• The node is a leaf – In other words, it does not have any children.

Let’s create assert functions for the above cases, we call those cases assertBoth, assertLeft, assertRight, assertLeaf

``````...

def assertBoth (self, tree, data):
self.assertEqual   (tree.data, data)
self.assertNotEqual(tree.left, None)
self.assertNotEqual(tree.right, None)

def assertLeft (self, tree, data):
self.assertEqual   (tree.data, data)
self.assertNotEqual(tree.left, None)
self.assertEqual   (tree.right,None)

def assertRight(self, tree, data):
self.assertEqual   (tree.data, data)
self.assertEqual   (tree.left, None)
self.assertNotEqual(tree.right,None)

def assertLeaf (self, tree, data):
self.assertEqual(tree.data, data)
self.assertEqual(tree.left, None)
self.assertEqual(tree.right, None)``````

### Writing tests with the assert Functions

Let’s write some test to level-based representation of binary tree. For simplicity, the data in tested lists will be their position in the list.

It is important to call the test in significant name. We use test followed by items of the list separated by _. we also use x instead of None to make the the name concise. This way, we can easilly see what the test function is about.

#### Test Empty List

The simplest list is the the empty list

`````` def test_load_empty(self):
self.assertEqual(tree, None)
``````

Now, let’s create tests for the following trees

#### Test List 

``````def test_load_0(self):
self.assertLeaf(tree,0)``````

#### Test List [0,1]

``````def test_load_0_1(self):
self.assertLeft(tree, 0)
self.assertLeaf(tree.left ,1 )``````

#### Test List [0,None,2]

``````def test_load_0_x_2(self):
self.assertRight(tree, 0)
self.assertLeaf(tree.right ,2 )``````

#### Test List test [0,1,2,None,4,5]

``````def test_load_0_1_2_x_4_5(self):
# level 0
self.assertBoth (tree            , 0)
# level 1
self.assertRight(tree.left       , 1)
self.assertLeft (tree.right      , 2)
# level 2
self.assertLeaf (tree.left.right , 4)
self.assertLeaf (tree.right.left , 5)``````

## Running The Tests

After we write the tests, It’s time run them. Let’s see how to run the tests and understand the report generated by unittest module.

Run the following command in the project root.

###### Runing tests of tests.load module
``python -m unittest tests.load``

You should get the following output:

###### Running tests of tests.load module
``````\$ python -m unittest tests.load
EEEE.
======================================================================
----------------------------------------------------------------------
Traceback (most recent call last):
self.assertLeaf(tree,0)
File "C:\projects\playground\tests\load.py", line 22, in assertLeaf
self.assertEqual(tree.data, data)
AttributeError: 'NoneType' object has no attribute 'data'
======================================================================
...
======================================================================
...
======================================================================
...
----------------------------------------------------------------------
Ran 5 tests in 0.001s

FAILED (errors=4)``````

### Understanding The unittest output

So, what this output tells us?

###### unittest – bottom summary message
``Ran 5 tests in 0.001s``

At the bottom of the output, we can see how many tests were running and the time it takes. In our case, we ran all the 5 tests in the tests.load module in 0.001 seconds.

###### unittest – last summary message
``FAILED (errors=4)``

We also see in the bottom of the output, whether we pass the test. There are two options to this summary message:

• The OK is displayed if all the tests were successful
• The FAILED (failures=X, errors=Y) if there at least one test that failed or ended with an error.

What is the difference between failure and an error:

• An error is when a test raises an exception (other than AssertionError)
• A failure is when an assertion does not hold and raises AssertionError, this can be from an assert statement or by calling one of the assertXXX function of unittest.TestCase

In our case, 4 tests ended with error – therefore we the second summary message is displayed.

###### unittest – detailed error message for test
``````======================================================================
----------------------------------------------------------------------
Traceback (most recent call last):
self.assertLeaf(tree,0)
File "C:\projects\playground\tests\load.py", line 22, in assertLeaf
self.assertEqual(tree.data, data)
AttributeError: 'NoneType' object has no attribute 'data'``````

For each error or failure, you can see :

• The status of the test. It can be ERROR or FAIL
• The name of the test. In our case, test_load_0
• The traceback of the exception, so you can easily see the line where the exception was raised
###### unittest – concise top summary results
``EEEE.``

At the top of the output. We can see concise summary results of all the ran tests. For each ran test, one character is displayed that shows the status of the test:

• . means the test passed
• F means the test failed. In other words, assertion in test did not hold
• E means the test ended with an error.

We can see that there is a test that passed without writing any code. Can you conclude what the test that passed is from the output?

The test_empty is passed since the load stub return the expected None. However, It is not enough – To write a correct code, all test needs to pass. Remember that even a broken watch shows the right time twice a day 🙂

## Solution to part 1 – Load Function

So, our 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 :

Do you see the pattern? It is easy to see:

Now that we recolonize 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 :

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?

### Refactoring and Improving The 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)

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 default from the outer function.

###### Refactoring code – simplify loadByIndex
`````` def load(data: List[Union[int, None]]):
# 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)

Now, that we have tests, we can be confident in refactoring the code.

###### Refactoring code – simplify loadByIndex
``````def load(data: List[Union[int, None]]):
# 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 Again
``````\$ 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?