Implementing Backward Iterator in BST

0 0 6 minutes read

Given a Binary search tree, the task is to implement backward iterator on it with the following functions.

curr(): returns the pointer to current element.
prev(): iterates to the previous largest element in the Binary Search Tree.
isEnd(): returns true if there’s no node left to traverse else false.

Iterator traverses the BST in decreasing order. We will implement the iterator using a stack data structure.

Initialisation:

We will create a stack named “q” to store the nodes of BST.

Create a variable “curr” and initialise it with pointer to root.

While “curr” is not NULL

Push “curr” in the stack ‘q’.

Set curr = curr -> right

curr()

Returns the value at the top of the stack ‘q’.
Note: It might throw segmentation fault if the stack is empty.

Time Complexity: O(1)

prev()

Declare pointer variable “curr” which points to node.

Set curr = q.top()->left.

Pop top most element of stack.

While “curr” is not NULL

Push “curr” in the stack ‘q’.

Set curr = curr -> right.

Time Complexity: O(1) on average of all calls. Can be O(h) for a single call in the worst case.

isEnd()

Returns true if stack “q” is empty else returns false.

Time Complexity: O(1)
Worst Case space complexity for this implementation of iterators is O(h). It should be noticed that
iterator points to the top-most element of the stack.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Node of the binary tree
struct node {
    int data;
    node* left;
    node* right;
    node(int data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};
 
// Iterator for BST
class bstit {
private:
    // Stack to store the nodes
    // of BST
    stack<node*> q;
 
public:
    // Constructor for the class
    bstit(node* root)
    {
        // Initializing stack
        node* curr = root;
        while (curr != NULL)
            q.push(curr), curr = curr->right;
    }
 
    // Function to return
    // current element iterator
    // is pointing to
    node* curr()
    {
        return q.top();
    }
 
    // Function to iterate to previous
    // element of BST
    void prev()
    {
        node* curr = q.top()->left;
        q.pop();
        while (curr != NULL)
            q.push(curr), curr = curr->right;
    }
 
    // Function to check if
    // stack is empty
    bool isEnd()
    {
        return !(q.size());
    }
};
 
// Function to test the iterator
void iterate(bstit it)
{
    while (!it.isEnd())
        cout << it.curr()->data << " ", it.prev();
}
 
// Driver code
int main()
{
    node* root = new node(5);
    root->left = new node(3);
    root->right = new node(7);
    root->left->left = new node(2);
    root->left->right = new node(4);
    root->right->left = new node(6);
    root->right->right = new node(8);
 
    // Iterator to BST
    bstit it(root);
 
    // Function call to test the iterator
    iterate(it);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
// Node of the binary tree
class node {
  int data;
  node left;
  node right;
  node(int data)
  {
    this.data = data;
    left = null;
    right = null;
  }
}
 
// Iterator for BST
class bstit
{
 
  // Stack to store the nodes
  // of BST
  Stack<node> q;
 
  // Constructor for the class
  public bstit(node root)
  {
 
    // Initializing stack
    q = new Stack<>();
    node curr = root;
    while (curr != null) {
      q.add(curr);
      curr = curr.right;
    }
  }
 
  // Function to return
  // current element iterator
  // is pointing to
  node curr()
  {
    return q.peek();
  }
 
  // Function to iterate to previous
  // element of BST
  void prev()
  {
    node curr = q.peek().left;
    q.pop();
    while (curr != null) {
      q.add(curr); 
      curr = curr.right;
    }
  }
 
  // Function to check if
  // stack is empty
  boolean isEnd()
  {
    return (q.size() != 0);
  }
 
  // Function to test the iterator
  void iterate(bstit it)
  {
    while (it.isEnd()) {
      System.out.print(it.curr().data);
      System.out.print(" ");
      prev();
    }
 
  }
}
public class GFG
{
 
  // Driver code
  public static void main(String[] args)
  {
    node root = new node(5);
    root.left = new node(3);
    root.right = new node(7);
    root.left.left = new node(2);
    root.left.right = new node(4);
    root.right.left = new node(6);
    root.right.right = new node(8);
 
    // Iterator to BST
    bstit it = new bstit(root);
 
    // Function call to test the iterator
    it.iterate(it);
 
  }
}
 
// This code is contributed by Rajput-Ji 

Python3

# Python 3 implementation of the approach
 
# Node of the binary tree
class node:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
 
# Iterator for BST
class bstit:
    # __stack to store the nodes
    # of BST
    __stack = []
    # Constructor for the class
 
    def __init__(self, root):
 
        # Initializing __stack
        curr = root
        while (curr is not None):
            self.__stack.append(curr)
            curr = curr.right
 
    # Function to return
    # current element iterator
    # is pointing to
    def curr(self):
        return self.__stack[-1]
 
    # Function to iterate to previous
    # element of BST
    def prev(self):
     
        curr = self.__stack[-1].left
        self.__stack.pop()
        while (curr != None):
            self.__stack.append(curr)
            curr = curr.right
 
    # Function to check if
    # __stack is empty
    def isEnd(self):
        return not len((self.__stack))
 
# Function to test the iterator
def iterate(it):
    while (not it.isEnd()):
        print(it.curr().data,end=" ")
        it.prev()
 
# Driver code
if __name__ == '__main__':
 
    root = node(5)
    root.left = node(3)
    root.right = node(7)
    root.left.left = node(2)
    root.left.right = node(4)
    root.right.left = node(6)
    root.right.right = node(8)
 
    # Iterator to BST
    it=bstit(root)
 
    # Function call to test the iterator
    iterate(it)
    print()
# This code is contributed by Amartya Ghosh

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
// Node of the binary tree
public class node {
  public int data;
  public node left;
  public node right;
 
  public node(int data) {
    this.data = data;
    left = null;
    right = null;
  }
}
 
// Iterator for BST
public class bstit {
 
  // Stack to store the nodes
  // of BST
  Stack<node> q;
 
  // Constructor for the class
  public bstit(node root) {
 
    // Initializing stack
    q = new Stack<node>();
    node curr = root;
    while (curr != null) {
      q.Push(curr);
      curr = curr.right;
    }
  }
 
  // Function to return
  // current element iterator
  // is pointing to
  public node curr() {
    return q.Peek();
  }
 
  // Function to iterate to previous
  // element of BST
  public void prev() {
    node curr = q.Peek().left;
    q.Pop();
    while (curr != null) {
      q.Push(curr);
      curr = curr.right;
    }
  }
 
  // Function to check if
  // stack is empty
  public bool isEnd() {
    return (q.Count != 0);
  }
 
  // Function to test the iterator
  public void iterate(bstit it) {
    while (it.isEnd()) {
      Console.Write(it.curr().data);
      Console.Write(" ");
      prev();
    }
 
  }
}
 
public class GFG {
 
  // Driver code
  public static void Main(String[] args) {
    node root = new node(5);
    root.left = new node(3);
    root.right = new node(7);
    root.left.left = new node(2);
    root.left.right = new node(4);
    root.right.left = new node(6);
    root.right.right = new node(8);
 
    // Iterator to BST
    bstit it = new bstit(root);
 
    // Function call to test the iterator
    it.iterate(it);
 
  }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript implementation of the approach
 
// Node of the binary tree
class node
{
    constructor(data) 
    {
        this.left = null;
        this.right = null;
        this.data = data;
    }
}
 
// Stack to store the nodes
// of BST
let q = [];
 
// Constructor for the class
function bstit(root)
{
     
    // Initializing stack
    let curr = root;
     
    while (curr != null)
    {
        q.push(curr);
        curr = curr.right;
    }
}
 
// Function to return
// current element iterator
// is pointing to
function curr()
{
    return q[q.length - 1];
}
 
// Function to iterate to previous
// element of BST
function prev()
{
    let curr = q[q.length - 1].left;
    q.pop();
     
    while (curr != null)
    {
        q.push(curr);
        curr = curr.right;
    } 
}
 
// Function to check if
// stack is empty
function isEnd()
{
    return (q.length == 0);
}
 
// Function to test the iterator
function iterate()
{
    while (!isEnd())
    {
        document.write(curr().data + " ");
        prev();
    }
}
 
// Driver code
let root = new node(5);
root.left = new node(3);
root.right = new node(7);
root.left.left = new node(2);
root.left.right = new node(4);
root.right.left = new node(6);
root.right.right = new node(8);
 
// Iterator to BST
bstit(root);
 
// Function call to test the iterator
iterate();
 
// This code is contributed by divyeshrabadiya07
 
</script>

Output:

8 7 6 5 4 3 2

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!