Playing with trees in Python

trees.py

#!/usr/bin/env python

from queue import Queue

# https://medium.com/the-renaissance-developer/learning-tree-data-structure-27c6bb363051

'''
Root - the topmost node of the tree
Edge - the link between two 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 length of the longest path to a leaf
Depth - the lenght of the path from a node to its root
'''

'''
Binary Tree
    A 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`.
'''


def sep(text):
    print(f'\n\n> Example {text} {"-" * 100}\n')


class BinaryTree:

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

    # example 2
    def insert_left(self, value):
        if self.left_child is None:
            self.left_child = BinaryTree(value)
        else:
            new_node = BinaryTree(value)
            new_node.left_child = self.left_child
            self.left_child = new_node

    # example 2
    def insert_right(self, value):
        if self.right_child is None:
            self.right_child = BinaryTree(value)
        else:
            new_node = BinaryTree(value)
            new_node.right_child = self.right_child
            self.right_child = new_node

    # example 3
    def pre_order_DFS(self):
        print(self.value, end=', ')
        if self.left_child:
            self.left_child.pre_order_DFS()
        if self.right_child:
            self.right_child.pre_order_DFS()

    # example 3
    def in_order_DFS(self):
        if self.left_child:
            self.left_child.in_order_DFS()
        print(self.value, end=', ')
        if self.right_child:
            self.right_child.in_order_DFS()

    # example 3
    def post_order_DFS(self):
        if self.left_child:
            self.left_child.post_order_DFS()
        if self.right_child:
            self.right_child.post_order_DFS()
        print(self.value, end=', ')

    # example 4
    def breadth_first_search(self):
        queue = Queue()
        queue.put(self)
        while not queue.empty():
            current_node = queue.get()
            print(current_node.value, end=', ')
            if current_node.left_child:
                queue.put(current_node.left_child)
            if current_node.right_child:
                queue.put(current_node.right_child)


# Example 1 ----------------------------------------------------------------------------------------------------
sep(1)
tree = BinaryTree('a')
print(tree.value)        # 'a'
print(tree.left_child)   # None
print(tree.right_child)  # None


# Example 2 ----------------------------------------------------------------------------------------------------
sep(2)

a_node = BinaryTree('a')
a_node.insert_left('b')
a_node.insert_right('c')

b_node = a_node.left_child
b_node.insert_right('d')

c_node = a_node.right_child
c_node.insert_left('e')
c_node.insert_right('f')

d_node = b_node.right_child
e_node = c_node.left_child
f_node = c_node.right_child

print(a_node.value)  # a
print(b_node.value)  # b
print(c_node.value)  # c
print(d_node.value)  # d
print(e_node.value)  # e
print(f_node.value)  # f


# Example 3 ----------------------------------------------------------------------------------------------------
sep('3: DFS')
'''
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.
    ” — Wikipedia

Given:
#                   1
#             .----/ \----.
#             2           5
#            / \         / \
#           3   4       6   7

    Pre-order Search : output > 1, 2, 3, 4, 5, 6, 7
                       Print the current node’s value. Go to the left child and print it.
                       Backtrack. Go to the right child and print it.

    In-order Search  : output > 3, 2, 4, 1, 6, 5, 7
                       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.

    Post-order Search: output > 3, 4, 2, 6, 7, 5, 1
                       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.
'''

root = BinaryTree(1)
root.insert_left(2)
root.insert_right(5)

b_node = root.left_child
b_node.insert_left(3)
b_node.insert_right(4)

c_node = root.right_child
c_node.insert_left(6)
c_node.insert_right(7)


print('\n<-- Pre order -->')
root.pre_order_DFS()
print('\n<-- In order -->')
root.in_order_DFS()
print('\n<-- Post order -->')
root.post_order_DFS()


# Example 4 ----------------------------------------------------------------------------------------------------
sep('4: BFS')
'''
BFS: Breadth-First Search —
    “is an algorithm for traversing or searching tree data structure.
     It starts at the tree root and explores the neighbor nodes first,
     before moving to the next level neighbours.
    ” — Wikipedia


Given:
#                    1
#              .----/ \----.
#              2           5
#             / \         / \
#            3   4       6   7

    1. So first we add the root node into the queue with the put method.
    2. We will iterate while the queue is not empty.
    3. Get the first node in the queue, print its value
    4. Add both left and right children into the queue (if the current node has children).
    5. Done. We will print each node‘s value level by level with our queue helper.
'''
root = BinaryTree(1)
root.insert_left(2)
root.insert_right(5)

b_node = root.left_child
b_node.insert_left(3)
b_node.insert_right(4)

c_node = root.right_child
c_node.insert_left(6)
c_node.insert_right(7)

root.breadth_first_search()


# Example 5 ----------------------------------------------------------------------------------------------------
sep('5: Binary Search Tree')
'''
A Binary Search Tree is sometimes called ordered or sorted binary trees
and it keeps its values in sorted order, so that lookup and other
operations can use the principle of binary search — Wikipedia

One important property of a Binary Search Tree is
    “A Binary Search Tree node‘s value is larger than the value of any
     descendant of its left child, and smaller than the value of any
     descendant of its right child
    ”.

Insert 50, 76, 21, 4, 32, 100, 64, 52 in that order:

#                   50
#             .----/ \----.
#             21          76
#            / \         / \
#           4   32      64  100
#                      /
#                     52
'''


class BinarySearchTree(BinaryTree):

    # example 5
    def insert_node(self, value):
        if value <= self.value and self.left_child:
            self.left_child.insert_node(value)
        elif value <= self.value:
            self.left_child = BinarySearchTree(value)
        elif value > self.value and self.right_child:
            self.right_child.insert_node(value)
        else:
            self.right_child = BinarySearchTree(value)

    # example 5
    def find_node(self, value):
        if value < self.value and self.left_child:
            return self.left_child.find_node(value)
        if value > self.value and self.right_child:
            return self.right_child.find_node(value)
        return value == self.value

    # example 6
    def remove_node(self, value, parent):
        if value < self.value and self.left_child:
            return self.left_child.remove_node(value, self)
        elif value < self.value:
            return False
        elif value > self.value and self.right_child:
            return self.right_child.remove_node(value, self)
        elif value > self.value:
            return False
        else:
            if self.left_child is None and self.right_child is None and self == parent.left_child:
                parent.left_child = None
                self.clear_node()
            elif self.left_child is None and self.right_child is None and self == parent.right_child:
                parent.right_child = None
                self.clear_node()
            elif self.left_child and self.right_child is None and self == parent.left_child:
                parent.left_child = self.left_child
                self.clear_node()
            elif self.left_child and self.right_child is None and self == parent.right_child:
                parent.right_child = self.left_child
                self.clear_node()
            elif self.right_child and self.left_child is None and self == parent.left_child:
                parent.left_child = self.right_child
                self.clear_node()
            elif self.right_child and self.left_child is None and self == parent.right_child:
                parent.right_child = self.right_child
                self.clear_node()
            else:
                self.value = self.right_child.find_minimum_value()
                self.right_child.remove_node(self.value, self)

            return True

    # example 6
    def clear_node(self):
        self.value = None
        self.left_child = None
        self.right_child = None

    # example 6
    def find_minimum_value(self):
        if self.left_child:
            return self.left_child.find_minimum_value()
        return self.value


bst = BinarySearchTree(15)
bst.insert_node(10)
bst.insert_node(8)
bst.insert_node(12)
bst.insert_node(20)
bst.insert_node(17)
bst.insert_node(25)
bst.insert_node(19)

print('Found 25', bst.find_node(25))
print('Found 10', bst.find_node(10))
print('Found 8', bst.find_node(8))
print('Found 12', bst.find_node(12))
print('Found 20', bst.find_node(20))
print('Found 17', bst.find_node(17))
print('Found 25', bst.find_node(25))
print('Found 19', bst.find_node(19))
print('Found 99', bst.find_node(99))


# Example 6 ----------------------------------------------------------------------------------------------------
sep('6: Deleteing in a Binary Search Tree')
'''
Case 1: a node with no children (leaf node)

#         50                                50
#      /      \                           /    \
#     30       70                       30     70
#   /    \                                \
#  20     40         (DELETE 20) --->     40


Case 2: a node with just one child (left or right child)

#         50                                50
#      /      \                           /    \
#     30       70    (DELETE 30) --->    20     70
#   /
#  20


Case 3: a node with two children; need to rebalance the tree.

#         50                                50
#      /      \                           /    \
#     30       70    (DELETE 30) --->    40     70
#   /    \                             /
#  20     40                          20


Given:

#         15
#      /      \
#     10       20
#   /    \    /    \
#  8     12   17   25
#              \
#               19

'''
print('\n<-- START -->')
print('In order: ')
bst.in_order_DFS()
print()
print('Breadth first: ')
bst.breadth_first_search()

print('\n<-- remove 8 -->')
print(bst.remove_node(8, None))  # True
bst.breadth_first_search()

#     |15|
#   /      \
# |10|     |20|
#    \    /    \
#   |12| |17| |25|
#          \
#          |19|

print('\n<-- remove 17 -->')
print(bst.remove_node(17, None))  # True
bst.breadth_first_search()

#        |15|
#      /      \
#    |10|     |20|
#       \    /    \
#      |12| |19| |25|

print('\n<-- remove 15 -->')
print(bst.remove_node(15, None))  # True
bst.breadth_first_search()

#        |19|
#      /      \
#    |10|     |20|
#        \        \
#        |12|     |25|