Python Binary Tree

python_binary_tree.py

""""
Trees

Trees are well known as a non-linear Data Structure. It doesn’t store data in a linear way. It organizes data in a hierarchical way.

- Root: the topmost node of the tree
- Edge: the link between 2 nodes
- Child: a node that has a parent node
- Parent: a node that has an edge to a child node
- Leaf: a node that does not have a child node in the tree
- Height: The height of a tree is the length of the longest path to a leaf.
- Depth: The depth of a node is the length of the path to its root.

Binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child

Ref --> https://medium.com/the-renaissance-developer/learning-tree-data-structure-27c6bb363051
"""
class BinaryTree:

    def __init__(self, value):
        self.value = value
        self.left_child = None
        self.right_child = None

    def insert_left(self, value):
        if self.left_child:
            node = BinaryTree(value)
            node.left_child = self.left_child
            self.left_child = node
        else:
            self.left_child = BinaryTree(value)

    def insert_right(self, value):
        if self.right_child:
            node = BinaryTree(value)
            node.right_child = self.right_child
            self.right_child = node
        else:
            self.right_child = BinaryTree(value)

    """
    DFS: Depth-First Search — “is an algorithm for traversing or searching tree data structure.
        One starts at the root and explores as far as possible along each branch before backtracking.”
    """
    def pre_order(self):
        """
        Print the current node’s value. Go to the left child and print it. Backtrack.
        Go to the right child and print it.
        """
        print(self.value)

        if self.left_child:
            self.left_child.pre_order()

        if self.right_child:
            self.right_child.pre_order()

    def in_order(self):
        """
        We go way down to the left child and print it first. Backtrack and print it.
        And go way down to the right child and print it.
        """
        if self.left_child:
            self.left_child.in_order()

        print(self.value)

        if self.right_child:
            self.right_child.in_order()

    def post_order(self):
        """
        We go way down to the left child and print it first. Backtrack.
        Go way down to the right child. Print it second. Backtrack and print it.
        """
        if self.left_child:
            self.left_child.post_order()

        if self.right_child:
            self.right_child.post_order()

        print(self.value)