Binary Tree ADT

`BinaryTree (Tree)`

A binary tree is a tree whose nodes contain a maximum of two children, the left child and the right child. The order of the children of any node is such that the left child has precedence over the right child. Binary tree vocabularies include, but are not limited to:

Proper/full binary tree - a binary tree whose nodes each have zero or two children
Balanced binary tree - a binary tree whose left and right subtrees heights differ by a maximum of one, with each of the left and right subtrees being recursively balanced
Complete binary tree - a binary tree whose levels are completely filled, except possibly for the last level whose nodes must be as far left as possible
Perfect binary tree - a binary tree whose internal nodes each contain two children, and the leaves are contained within the same level

`get_left_child(self, position)`

Return the left child of the given position. Time complexity: O(1).

Parameters:

Name	Type	Description	Default
`position`	`_Position`	position containing the node whose left child is being sought	required

Returns:

Type	Description
`Optional[tree.Tree._Position]`	the position of the left child of the node contained in the passed position. None if the position has no left child.

Source code in trees/binary_tree.py

def get_left_child(self, position: Tree._Position) -> Union[Tree._Position, None]:
    """Return the left child of the given position. Time complexity: O(1).

    :param position: position containing the node whose left child is being sought
    :returns: the position of the left child of the node contained in the passed position. None if the position has
    no left child.
    """
    if not position.is_owned_by(self):
        raise ValueError("Position doesn't belong to this tree")

    node = position.manipulate_node(self, "_validate_node")
    children = node.children

    if children is None:
        return None
    else:
        left_child = children[0]
        return Tree._Position(self, left_child) if left_child is not None else None

`get_right_child(self, position)`

Return the right child of the given position. Time complexity: O(1).

Parameters:

Name	Type	Description	Default
`position`	`_Position`	position containing the node whose right child is being sought	required

Returns:

Type	Description
`Optional[tree.Tree._Position]`	the position of the right child of the node contained in the passed position. None if the position has no right child.

Source code in trees/binary_tree.py

def get_right_child(self, position: Tree._Position) -> Union[Tree._Position, None]:
    """Return the right child of the given position. Time complexity: O(1).

    :param position: position containing the node whose right child is being sought
    :returns: the position of the right child of the node contained in the passed position. None if the position has
    no right child.
    """
    if not position.is_owned_by(self):
        raise ValueError("Position doesn't belong to this tree")

    node = position.manipulate_node(self, "_validate_node")
    children = node.children

    if children is None:
        return None
    else:
        right_child = children[1]
        return (
            Tree._Position(self, right_child) if right_child is not None else None
        )

`insert(self, key, value)`

Insert a value into the tree

Parameters:

Name	Type	Description	Default
`key`		unique identifier of the item to be added to the tree	required
`value`		item to be added to the tree	required

Source code in trees/binary_tree.py

@abstractmethod
def insert(self, key, value):
    super().insert(key, value)

`traverse_subtree_in_order(self, position)`

In-order traverse subtree whose root is the passed position and return a generator of the positions it contains

Parameters:

Name	Type	Description	Default
`position`	`_Position`	position containing the node that's the root of the subtree to be traversed	required

Returns:

Type	Description
`Generator`	a generator of the positions

Source code in trees/binary_tree.py

def traverse_subtree_in_order(self, position: Tree._Position) -> Generator:
    """In-order traverse subtree whose root is the passed position and return a generator of the positions it
    contains

    :param position: position containing the node that's the root of the subtree to be traversed
    :returns: a generator of the positions
    """
    if not position.is_owned_by(self):
        raise ValueError("Position doesn't belong to this tree")

    left_child = self.get_left_child(position)
    right_child = self.get_right_child(position)

    if left_child is not None:
        for i in self.traverse_subtree_in_order(left_child):
            yield i

    yield position

    if right_child is not None:
        for i in self.traverse_subtree_in_order(right_child):
            yield i

`traverse_tree_in_order(self)`

In-order traverse tree and return a generator of the positions it contains

Returns:

Type	Description
`Generator`	a generator of the positions

Source code in trees/binary_tree.py

def traverse_tree_in_order(self) -> Generator:
    """In-order traverse tree and return a generator of the positions it contains

    :returns: a generator of the positions
    """
    position = self.get_root()

    if position is not None:
        for i in self.traverse_subtree_in_order(position):
            yield i