Implementing Forward Iterator in BST

Developing a forward iterator for a Binary Search Tree (BST) entails developing a class that permits tree traversal in a particular order, typically ascending. The iterator needs to be able to go from the smallest to the largest element in the BST.

1. Understanding Binary Search Trees:

A Binary Search Tree is a hierarchical data structure that stores data so that quick lookup, addition, and removal of items is possible.

The key ideas:

• Each Node stores a key (like an integer) and additional data.
• Nodes are organized hierarchically such that the keys to the left of any node are less than that Node's key, and the keys to the right are greater.
• Looking up whether a key exists is very fast - the tree can be traversed quickly based on comparisons at each Node.
• Adding and removing nodes also relies on comparisons during traversal to find the correct spot in the hierarchy to insert or remove.

2. Node and Tree Structure:

Here is an explanation of the Node and tree structure in a Binary Search Tree (BST):

Nodes:

• Basic building blocks that store data in the tree.
• Each Node contains:
• Key: unique identifier used to sort data (e.g. integer).
• Value: actual data being stored.
• Left: pointer to the left child node.
• Right: pointer to the right child node.
• Parent: pointer to parent node.

Tree Structure:

• Root Node: The root node is the tree's highest Node.
• Child Nodes: Nodes directly connected below another node.
• Leaf Node: Nodes at the bottommost level with no children.
• Edge: Connection between one Node and another.
• Path: Series of edges from one Node to another.
• Height: Number of edges from the root to the bottommost Node.
• Depth: Number of edges from a node to the root
• Level: Layer number counting from root (starts at 0)

The hierarchical structure with key comparisons between parents' left & right children enables fast sorting, insertions and deletions. The objective is to implement a forward iterator with the following functions on a Binary search tree.

curr():

The curr() function in a Binary Search Tree (BST) implementation is used to access the Node currently being pointed to during traversal.

Specifically:

• It returns a pointer to the BST node that is considered the "current" Node that the traversal inspects.
• It allows the caller to easily access the key, value, and other data stored within this current Node as needed.

Some key things to note about curr():

• It is typically called repeatedly from inside a loop, traversing the BST to access each Node.
• It usually iterates by calling next() on each iteration to update the pointer to the next Node in sequence.
• The pointer returned by curr() is often cached locally with each loop iteration rather than calling curr() multiple times.
• Checking if curr() returns null is a common way to detect if the traversal has reached the end of the tree.

next()

The next() Function in a Binary Search Tree (BST) implementation is used to iterate through the tree during a traversal, updating the current Node to the next Node in sequence according to the rules of the traversal order.

Specifically, next() does the following key things:

• Updates the pointer to the "current" Node in the traversal to point to the successor node, per the traversal ordering rules.
• For BSTs, this ordering is typically an in-order traversal that visits the left branch, current Node, and right branch in sorted order.
• To find the next Node, it looks at the right child of the current Node and finds the left-most Node under it.
• If no right child exists, it traverses up parent pointers until finding a parent that is the left child of its parent.
• By repetitively calling next() inside a loop, all nodes in the BST can be visited in order.

isEnd()

The isEnd() function in a Binary Search Tree (BST) implementation is used to check if the traversal of the tree has reached the end.

Specifically, it does the following:

• Check whether the current node pointer maintained during the traversal has become null.
• It returns a boolean true if the current Node is null, indicating traversal has reached the end.
• Returns false if the current Node points to a valid node in the tree.

It is useful because:

• Traversals through iterative BST data structures require a way to detect when the end has been reached.
• Rather than checking if the current Node equals some sentinel value, checking for the null pointer is cleaner.
• It abstracts away the pointer-checking logic from caller code, encapsulating end detection in the BST class.

So, in essence, isEnd() provides a simple interface to check whether the iterative BST traversal has been completed. Comparing its return value against the null pointer indicator is cleaner than exposing pointer-checking logic across code.

Typical usage would be:

It makes writing iterative BST traversals simpler and cleaner for the caller.

C++ program that implements a forward iterator for a binary search tree (BST)

Output:

2 3 4 5 6 7 8