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
Binary Tree of List Representation []
Binary Tree of List Representation []
Binary Tree of List Representation [0,1]
Binary Tree of List Representation [0,1]
Binary Tree of List Representation [0]
Binary Tree of List Representation [0]
Binary Tree of List Representation [0,1,2,None,4,5]]
Binary Tree of List Representation [0,1,2,None,4,5]]
Binary Tree of List Representation [0,1,2,3,4,5,6,7]
Binary Tree of List Representation [0,1,2,3,4,5,6,7]
Binary Tree of List Representation [0,None,2]]
Binary Tree of List Representation [0,None,2]
Binary Tree of List Representation [0,None,2,None,None,None,6]
Binary Tree of List Representation [0,None,2,None,None,None,6]

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

Load tree from list
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 = tree.load([0])
...
>>> 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 load
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

tests/load.py
import unittest

from tree import load 
class TestLoad(unittest.TestCase):
  ...

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

tests/load.py – assert functions
...
class TestLoad(unittest.TestCase):

  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

Binary Tree of List Representation []
Binary Tree of List Representation []
tests/load.py – test []
 def test_load_empty(self):
     tree = load([])
     self.assertEqual(tree, None)    

Now, let’s create tests for the following trees

Test List [0]

Binary Tree of List Representation [0]
Binary Tree of List Representation [0]
tests/load.py – test [0]
def test_load_0(self):
    tree = load([0])
    self.assertLeaf(tree,0)

Test List [0,1]

Binary Tree of List Representation [0,1]
Binary Tree of List Representation [0,1]
tests/load.py – test [0,1]
def test_load_0_1(self):
    tree = load([0,1])
    self.assertLeft(tree, 0)
    self.assertLeaf(tree.left ,1 )

Test List [0,None,2]

Binary Tree of List Representation [0,None,2]]
Binary Tree of List Representation [0,None,2]
tests/load.py – test [0,None,2]
def test_load_0_x_2(self):
    tree = load([0,None,2])
    self.assertRight(tree, 0)
    self.assertLeaf(tree.right ,2 )

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

Binary Tree of List Representation [0,1,2,None,4,5]]
Binary Tree of List Representation [0,1,2,None,4,5]]
tests/load.py – test [0,1,2,None,4,5]
def test_load_0_1_2_x_4_5(self):
    tree = load([0,1,2,None,4,5])
    # 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.
======================================================================
ERROR: test_load_0 (tests.load.TestLoad)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "C:\projects\playground\tests\load.py", line 32, in test_load_0
    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'
======================================================================
ERROR: test_load_0_1 (tests.load.TestLoad)
...
======================================================================
ERROR: test_load_0_1_2_x_4_5 (tests.load.TestLoad)
...
======================================================================
ERROR: test_load_0_x_2 (tests.load.TestLoad)
...
----------------------------------------------------------------------
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
======================================================================
ERROR: test_load_0 (tests.load.TestLoad)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "C:\projects\playground\tests\load.py", line 32, in test_load_0
    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 name of the test case. In our case, tests.load.TestLoad
  • 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 :

Node indexLeft child indexRight child index
012
134
156
378
4910

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

Node indexLeft child indexRight child index
k2*k+12*k+2

Now that we recolonize the pattern, we can write:

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

The 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?

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

Refactoring code – adding 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 default from the outer function.

Refactoring code – simplify 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.

Refactoring code – simplify 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 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?

Leave a Reply

Your email address will not be published. Required fields are marked *