Decreasing Time Complexity With Binary Search Tree In Python 3

Published in

The Startup

5 min readMay 8, 2020

Imagine a scenario where a task is given; to find a watermelon weighing one hundred pounds among one hundred identical looking watermelons with different weight sorted by weight lightest to heaviest (each watermelon is a pound heavier than the prior, the first watermelon is one pound) and take the least amount of time doing so. The only way to check the weight of the watermelon is to weigh it out one by one. Each time a watermelon is weighed, five seconds go by. One method is to weigh out each watermelon until the watermelon that weighs one hundred pounds is found. By doing that five hundred seconds have passed. This method could not be implemented in large databases because there is simply way too much data to iterate one by one through. The more efficient way to search through massive data is by implementing binary search tree.

What is it?

A binary search tree is a data structure where each node has at most two children. This data structure has many advantages such as fast search, insertion, and deletion time, sorting the nodes as it goes, and not needing to relocate memory.

What is it made of?

A binary tree can be taken apart into nodes and edges.

Nodes

Nodes can be identified as either the root, parent, child, leaf, ancestor, descendant, or internal node. The root node is the top most node. If referring to the binary tree image above, it would be node 8. Parent nodes are nodes with one or more child nodes which are nodes that are being pointed at as left or right node by a preceding node. Leaf nodes are nodes that do not have children. A parent node can be a child node and vice versa. A child node can be a leaf node but a parent node cannot. Examples of parent nodes from the image above are nodes 8, 3, 10, 6, and 14. Examples of child nodes are nodes 3, 10, 1, 6, 14, 4, 7, and 13. Examples of leaf nodes are nodes 1, 4, 7, and 14. Nodes can be used to calculate the size of the tree, and it’s as simple as counting all the nodes (unless there is a variable that logs each time a change is made but that is a different subject).

Edges

Edges are what connect the nodes together. Using the tree’s edges, the height (tree), height (node), depth , and level can be calculated. The height (tree) of the tree is the number of edges in the longest path the tree has from the root to the leaf. The height (node) of the tree is the number of edges in the longest path the tree has from the current node to leaf. The depth is the number of edges between the current node and the root. The level is depth plus one.

How does it work?

The locomotion of a binary search tree is fairly simple. Referring to the watermelon scenario above, the known facts about the watermelons are that the watermelons are sorted by weight, the watermelon being searched for weighs one hundred pounds, and there are one hundred watermelons. The first watermelon that will be weighed is the watermelon that is in the middle of the list, so watermelon 50 (root node). Watermelon 50’s left pointer will point to a watermelon that weighs less than itself (left child node), so every watermelon to the left of watermelon 50 can now be ignored. The next watermelon that will be weighed will be the watermelon being pointed by 50’s right pointer (right child node). Repeating the process will not only find the watermelon that weighs one hundred pounds, the time needed to search for the watermelon has been decreased.

Code

There are two ways of going about binary search tree; iterative and recursive.

Iterative

def find_node_iterative(self, item):
    node = self.root
    while node is not None:
        if node.data == item:
            return node
        elif node.data < item:
            node = node.right
        elif node.data > item:
            node = node.left
    return None

Iterative can be written by passing in a parameter item (what is being searched for). Next, make a node variable and set it equal to the root of the binary tree (self.root). Then check

If the current node’s data (node.data) is equal to the item and if it is return the node
If not check to see if the node’s data is lesser than the item and if it is set the node to equal the right node (node.right)
Or if the data is greater set the node to equal the left node (node.left)

all inside of a while loop checking if the node exists (to see if the previous node was a leaf node). The while loop will run as long as there is a node to check, but None can be returned in the condition where the node doesn’t exist.

Recursive

def find_node_recursive(self, item, node):
    if node is None:
        return None
    elif node.data == item:
        return node
    elif node.data < item:
        return find_node_recursive(self, item, node.right)
    elif node.data > item:
        return find_node_recursive(self, item, node.left)

Recursive can be written by passing in the parameters item (what is being searched for) and node (root node). The steps to the recursive function are

Checking if the node exists
If it does, check if the current node’s data (node.data) is equal to the item and if it is return the node
If it is not check if the current node’s data is less than the item and if it is return the recursive function but this time set the node parameter as the right node (node.right)
If it is not less than then the item check if it is greater than the item and if it is return the recursive function but this time set the node parameter as the left node (node.left)

Time Complexity

The best case time complexity for both the iterative and recursive methods are O(1). In this case the root node’s data is equal to the item being searched for, therefore being constant time. The worst case for both methods are O(log n). In this case the item being searched for is a leaf node, and the tree must constantly be divided by half until the item is found, therefore being logarithmic running time.

🍉 Conclusion 🍉

The time spent looking for an item in a binary search tree varies by size of the tree. When working with small databases, an iterative method can be perfectly fine, but when working with large databases, the binary search tree method is preferred.

References

“Binary Tree Data Structure.” GeeksforGeeks, www.geeksforgeeks.org/binary-tree-data-structure/.
Davis, Alan, and Dahmen, Jessamyn. “CS1.3 Core Data Structures — Trees & Binary Search Trees.” GitHub, Make School, 28 May 2019, github.com/Make-School-Courses/CS-1.3-Core-Data-Structures/blob/master/Lessons/TreesBinarySearchTrees.md.

Images