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 :
Each level is ordered from left to right. so:
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:
Let's see some samples. In the following graphs:
The tree | The list |
---|---|
![]() |
[0,1,2,3,4,5,6] |
![]() |
[0] |
![]() |
[0,1,2,None,4,5] |
![]() |
[0,None,2] |
![]() |
[0,1] |
![]() |
[] |
![]() |
[0,None,2,None,None.5] |
![]() |
[0,None,2,None,None,None,6] |
Given the following Node class:
class Node:
def __init__(self,data,left,right):
self.data = data
self.left = left
self.right = right
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
Write a function that takes a the root node of a binary tree and return its level-based representation
def dump(tree : Node) -> List[Union[int,None]]:
pass