BST: Binary Search Tree

Binary Search Tree is based on the property that right child is bigger than the parent, and the left child is smaller. When binary tree is generated this is always true. Therefore, when search for an item, we can use this property and make searching process simpler instead of checking all the items in the tree.

The successor is the node that are next-largest. Because of the property of tree, we can conclude that there are three cases when look for an item.

1. If the node has a right child, then the successor is the smallest key in the right subtree.
2. If the node has no right child and is the left child of its parent, then the parent is the successor.
3. If the node is the right child of its parent, and itself has no right child, then the successor to this node is the successor of its parent, excluding this node.

When deleting the node from the tree, we can use the case 1. Also, from the property of tree, we can conclude that the smallest number in the tree will be the left-most child. This is true because left child is always smaller than its parent. Then, again, the left child of left child will be smaller than the first left child, and so on. Thus, the left-most child is the smallest in the tree. Therefore, we can write a function that finds a minimum value in tree as follows:

def _find_min(node: BTNode) -> BTNode:
    '''Find and return minimal node, assume node is not None'''
    return _find_min(node.left) if node.left else node

This is a part of the code from the class BTNode and details omitted. Since finding maximum has been discussed in the class, I tried out finding a minimum based on the lecture. Notice that the only the left children are checked, and the process is recursive.

There are more things that can be done using Binary Search Tree. So, understanding this will be a crucial when it comes to data structures.