Binary search tree and Big O ( Week 8)

We learn Binary search tree this week. It is very important for us when we need do a large numbers of search. Like we know the run time is O(log n).

There are 4 basic conditions for Binary search tree:

1. The left subtree of a node contains only nodes with keys less than the node's key.

2. The right subtree of a node contains only nodes with keys greater than the node's key.

3. The left and right subtree each must also be a binary search tree.

4. There must be no duplicate nodes.

In our TUT, we also practiced to use Binary Search Tree. 

Here is our example:

We wrote _count_less function for helping count_less function.

    def count_less(self: 'BST', value: object) -> int:

        """

        Return the number of values in this BST that are strictly 
        less than value.

        """

        return BST._count_less(self.root, value)  # stub

    

    def _count_less(root: '_BSTNode', value: object) -> int:

        if root:

            if value > root.value:

                return  BST._count_less(root.left, value) + 1 \
                        + BST._count_less(root.right, value)

            else:   

                return BST._count_less(root.left, value)

        return 0