Level based Representation of a Binary Tree

We say that a level-based 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

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
The tree The list
binary tree graph [0,1,2,3,4,5,6]
binary tree graph [0]
binary tree graph [0,1,2,None,4,5]
binary tree graph [0,None,2]
binary tree graph [0,1]
binary tree graph []
binary tree graph [0,None,2,None,None.5]
binary tree graph [0,None,2,None,None,None,6]

The quiz

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
python quiz