Implementing Backward Iterator in BST

Introduction-  

This blog will discuss how to implement a backward iterator in BST. Before moving further, let's see what a BST is.

"BST (Binary Search Tree) is a special binary tree in which there is a condition that all the nodes in the left subtree of any node will have a value less than that of the node and all the nodes in the right subtree of the node will have a value greater than the value of the node."

See Difference Between Binary Tree and BST

Now, let's understand what we have to implement:

We will be given a binary search tree (BST), and we have to implement a backward iterator on it with the following functions:

1. current() - It will return the pointer to the current element of the given BST
2. previous() - It will iterate to the previous largest element in the given BST
3. isLast() - It will return true if all the nodes are traversed, and there is no node left to go; else, it will return false.

Also, the iterator should traverse the given binary search tree in decreasing order.

Now, we have understood what we need to implement. In the next section, we will discuss the approach to implementing these.

Also see, Data Structures

Solution Approach

This article will see how we can implement a backward iterator in BST. The backward iterator will be traversing the BST in decreasing order. To implement the backward iterator in BST, we need to create three functions. The first function will be used to return the iterator to the current element, the second function will be used to take the backward iterator to the previous largest element in the BST, and the third function will be used to keep track what we have traversed all the nodes of the BST. We are creating a function to return an iterator to the previous largest element because the iterator we are going to implement is a backward iterator and will traverse the BST in decreasing order.

The approach is to use a stack data structure to store the nodes of the BST. First, we will store the nodes starting with the root node and will go to the right child only at each step and will store them. We are storing the nodes in this manner because the iterator will traverse the BST in decreasing order. In this stack, the top node will always be the current node. Now in the function "previous()", forgetting the previous largest node, we will start from the left of the current node and will go to its rightmost node as it will be the previous node having the largest value. And, for the third function, "isLast()", we can check the stack size. If the stack size is zero, it means there are no nodes left to traverse, so return true.

Algorithm 

Step 1. Create a class "Node" for creating the tree.

Step 2. Create a class "bstIterator" to create a backward iterator in BST, which will traverse the BST in decreasing order. 

Step 3. Inside the "bstIterator" class, create a stack to store nodes of the BST and a constructor for constructing the backward iterator for the given BST. Inside the constructor, insert the nodes of BST into the stack starting from the root node, going to the right child of each until getting a "NULL" node. 

Step 4.  Next, create a "current()" function inside the "bstIterator" class to return the iterator pointing to the current element of BST. Return the node at the top of the stack.

Step 5. Next, create a "previous()" function that will take the iterator to the previous largest element in the BST. Inside this function, we will go to the rightmost node of the left of the current node as it will be the largest previous element and will keep storing the nodes which will come in the path into our stack.

Step 6.  Next, create a function "isLast()" to check whether we have reached the last node and there are no more nodes left to traverse in the BST or not. It will return true if there are no nodes left to traverse; else, it will return false.

C++ code

// C++ implementation of backward iterator in BST
#include <bits/stdc++.h>
using namespace std;


//  "Node" class for creating binary tree
class Node {
public:
	int data;
	Node* left;
	Node* right;

	Node(int val) {
		this->data = val;
		this->left = NULL;
		this->right = NULL;
	}
};


// Create a class for implementing backward Iterator for BST
class bstIterator {

// Declaring a Stack to store the nodes of BST
	stack<Node*> s;


   Public:


// Constructor for the class
	bstIterator(Node* root)
	{


// Inserting the nodes of BST into the stack
		Node* currentNode = root;
		while (currentNode != NULL)
		{
			s.push(currentNode);
			currentNode = currentNode->right;
		}
	}


// Function to return the iterator pointing to the current element
	Node* current()
	{
		return s.top();
	}


// Function to iterate to the previous largest element of BST
	void previous()
	{
		Node* currentNode = s.top()->left;
		s.pop();
		while (currentNode != NULL)
		{
			s.push(currentNode);
			currentNode = currentNode->right;
		}
	}


// Function to check if there is no nodes left to traverse
	bool isLast()
	{
		if (s.size() == 0) {
			return true;
		}
		return false;
	}
};


// Function to iterate the BST using the backward iterator in BST
void iterateBST(bstIterator itr)
{
	while (!itr.isLast())
	{
		cout << itr.current()->data << " ";
		itr.previous();
	}
}


// Driver code
int main()
{
	Node* root = new Node(4);
	root->left = new Node(2);
	root->right = new Node(6);
	root->left->left = new Node(1);
	root->left->right = new Node(3);
	root->right->left = new Node(5);
	root->right->right = new Node(7);


// Call the Constructor to create a backward iterator to the given BST
	bstIterator it(root);


// Call Function to iterate the BST using the backward iterator that we have created in the previous step
	iterateBST(it);


	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:
7 6 5 4 3 2 1 

Algorithm Complexity

Time Complexity: O(H)

In the class "bstIterator" used to implement a backward iterator in BST, the following three functions are created:

1. current(): It is taking constant time, so time complexity will be O(1).
2. previous(): In this function, we have used a "while loop" in which we are traversing the levels of the tree as we are going to the rightmost child, so the time complexity will be O(H), where 'H' is the height of the tree.
3. isLast(): It is taking constant time, so time complexity will be O(H), where 'H' is the height of the tree.

The overall time complexity of the implementation of a backward iterator in BST will be O(H), where 'H' is the height of the tree.

Space Complexity: O(H) 

In the class "bstIterator" used to implement a backward iterator in BST, we have used a stack in which at a time we are storing one node from each level, so worst case space complexity will be O(H) where 'H' is the height of the tree.

You can also read about insertion into bst.