I'm learning to use mypy and static type checkers while practicing algorithms and data structures.
In a Binary Search Tree, a Node is initialized with no children. They are of type Node. However, it seems that None is its own object type in Python so mypy gives me an error below. Is it possible to initialize the unassigned children as type Node?
binary_search_tree.py:17: error: Incompatible types in assignment (expression has type "None", variable has type "Node")
binary_search_tree.py:18: error: Incompatible types in assignment (expression has type "None", variable has type "Node")
Found 2 errors in 1 file (checked 1 source file)
Code below:
class Node:
# A node has a value which is an int and two children which are nodes
def __init__(self, value: int):
self.value: int = value
self.left: Node = None
self.right: Node = None
Because these values can be None
at times, you should instead specify them as Optional
types and then perform explicit None
checks when using them so that mypy
will know that they have a value. More information from mypy
's docs here:
from typing import Optional
class Node:
# A node has a value which is an int and two children which are nodes
def __init__(self, value: int):
self.value: int = value
self.left: Optional[Node] = None
self.right: Optional[Node] = None
It is otherwise impossible to declare them as only a Node
type if you initialize them as None
. Another option would be to create a NullNode
(or something similar) subclass which still has the type Node
but signifies that there is no Node
there:
class Node:
# A node has a value which is an int and two children which are nodes
def __init__(self, value: int):
self.value: int = value
self.left: Node = NullNode()
self.right: Node = NullNode()
class NullNode(Node):
pass