Skip to main content

Iterative Methods

This section looks at the functions that are implemented iteratively (or the iterative version of the functions)

Insert - Iterative version

This function will insert data into the tree. There are two ways to implement this function, either iteratively or recursively. We will start by looking at the iterative solution. In this situation, we begin by taking care of the empty tree situation. If the tree is empty we simply create a node and make root_ point to that only node. Otherwise, we need to go down our tree until we find the place where we must do the insertion and then create the node.

class BST:
class Node:
# Node's init function
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right

# BST's init function
def __init__(self):
self.root = None

def insert(self, data):
if self.root is None:
self.root = BST.Node(data)
else:
# curr points to the variable we are currently looking at
curr = self.root
inserted = False

while not inserted:
if data < curr.data:
if curr.left is not None:
curr = curr.left
else:
curr.left = BST.Node(data)
inserted = True
else:
if curr.right is not None:
curr = curr.right
else:
curr.right = BST.Node(data)
inserted = True

Search - Iterative version

The key operation that is supported by a binary search tree is search. For our purposes we will simply look at finding out whether or not a value is in the tree or not. The search operation should never look at the entire tree. The whole point of the binary search tree is to make this operation fast. We should search it so that we can eliminate a portion of the tree with every search operation.

To do this we start at the root and compare that node's data against what we want. If it matches, we have found it. If not, we go either left or right depending on how data relates to the current node. If at any point we have an empty tree (ie the pointer we are using for iterating through the tree becomes nullptr) we stop the search and return false. If we find a node that matches we stop and return true.

class BST:
class Node:
# Node's init function
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right

# BST's init function
def __init__(self):
self.root = None

def search(self, data):
curr = self.root

while curr is not None:
if data < curr.data:
curr = curr.left
elif data > curr.data:
curr = curr.right
else:
return curr

return None

Breadth First Print

Writing a breadth-first traversal involves using the queue data structure to order what nodes to deal with next. You want to deal with the nodes from top to bottom left to right, and thus you use the queue to order the nodes. Here is an example of how we will do this.

We begin by declaring a queue (initially empty)

Initial Empty Queue

Prime the Queue

We start prime the queue by putting the root into the queue. In this example, we always check to ensure no nullptrs are ever added to the queue. Alternatively we allow the addition of nullptrs and decide how to deal with them when we dequeue.

Prime the queue

Dequeue front of node and process it by adding its non-nullptr children into the queue, print the node

remove front node (20) and add 20&#39;s left and right children to queue, print 20

Continue by dequeuing front node and processing it in same manner

remove front node (10) and add 10&#39;s left and right children to queue, print 10

Repeat again as 25 only has a right child only it is added

Repeat again as 25 only has a right child only it is added

Repeat once again with 5 which has no children thus nothing is added to queue

Repeat once again with 5 which has no children thus nothing is added to queue

Repeat again with 15 (also no children)

Repeat again with 15 (also no children)

Repeat with 35 and add its children

Continue by removing 30

And one more time with 40

At this point queue is empty and thus, we have completed our breadthfirst print of the tree.

In code form, this is how we will write our code (we assume we have a template queue available:

import queue

class BST:
class Node:
# Node's init function
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right

# BST's init function
def __init__(self):
self.root = None

def breadth_first_print(self):
the_nodes = queue.Queue()

if self.root is not None:
the_nodes.put(self.root)

while not the_nodes.empty():
curr = the_nodes.get()

if curr.left:
the_nodes.put(curr.left)
if curr.right:
the_nodes.put(curr.right)

print(curr.data, end=" ")