Implementing Forward Iterator in BST
Given a Binary search tree, the task is to implement forward iterator on it with the following functions.
- curr(): returns the pointer to current element.
- next(): iterates to the next smallest element in the Binary Search Tree.
- isEnd(): returns true if there no node left to traverse else false.
Iterator traverses the BST in sorted order(increasing). 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 -> left
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)
next()
- Declare pointer variable “curr” which points to node.
- Set curr = q.top()->right.
- Pop top most element of stack.
- While “curr” is not NULL
- Push “curr” in the stack ‘q’.
- Set curr = curr -> left.
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 return 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->left; } // Function to return // current element iterator // is pointing to node* curr() { return q.top(); } // Function to iterate to next // element of BST void next() { node* curr = q.top()->right; q.pop(); while (curr != NULL) q.push(curr), curr = curr->left; } // Function to check if // stack is empty bool isEnd() { return !(q.size()); } }; // Function to iterator to every element // using iterator void iterate(bstit it) { while (!it.isEnd()) cout << it.curr()->data << " " , it.next(); } // 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 to test iterator iterate(it); return 0; } |
Java
// Java implementation of the approach import java.util.*; // Node of the binary tree class TreeNode { int val; TreeNode left; TreeNode right; TreeNode( int x) { val = x; } } // Iterator for BST class BSTIterator{ // Stack to store the nodes // of BST Stack<TreeNode> s; // Constructor for the class public BSTIterator(TreeNode root) { // Initializing stack s = new Stack<>(); TreeNode curr = root; while (curr != null ) { s.push(curr); curr = curr.left; } } // Function to return // current element iterator // is pointing to TreeNode curr() { return s.peek(); } // Function to iterate to next // element of BST public void next() { TreeNode temp = s.peek().right; s.pop(); while (temp != null ) { s.push(temp); temp = temp.left; } } // Function to check if // stack is empty public boolean isEnd() { return !s.isEmpty(); } // Function to iterator to every element // using iterator void iterate() { while (isEnd()) { System.out.print(curr().val + " " ); next(); } } } class BinaryTree{ TreeNode root; // Driver code public static void main(String args[]) { // Let us construct a tree shown in // the above figure BinaryTree tree = new BinaryTree(); tree.root = new TreeNode( 5 ); tree.root.left = new TreeNode( 3 ); tree.root.right = new TreeNode( 7 ); tree.root.left.left = new TreeNode( 2 ); tree.root.left.right = new TreeNode( 4 ); tree.root.right.left = new TreeNode( 6 ); tree.root.right.right = new TreeNode( 8 ); // Iterator to BST BSTIterator it = new BSTIterator(tree.root); // Function to test iterator it.iterate(); } } // This code is contributed by nobody_cares |
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.left # Function to return # current element iterator # is pointing to def curr( self ): return self .__stack[ - 1 ] # Function to iterate to next # element of BST def next ( self ): curr = self .__stack[ - 1 ].right self .__stack.pop() while (curr is not None ): self .__stack.append(curr) curr = curr.left # Function to check if # stack is empty def isEnd( self ): return not len ( self .__stack) # Function to iterator to every element # using iterator def iterate(it): while ( not it.isEnd()): print (it.curr().data,end = " " ) it. next () # 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 to test iterator iterate(it) print () # This code is added by Amartya Ghosh |
C#
// C# implementation of the approach using System; using System.Collections.Generic; // Node of the binary tree public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode( int x) { val = x; } } // Iterator for BST public class BSTIterator{ // Stack to store the nodes // of BST Stack<TreeNode> s; // Constructor for the class public BSTIterator(TreeNode root) { // Initializing stack s = new Stack<TreeNode>(); TreeNode curr = root; while (curr != null ) { s.Push(curr); curr = curr.left; } } // Function to return // current element iterator // is pointing to TreeNode curr() { return s.Peek(); } // Function to iterate to next // element of BST public void next() { TreeNode temp = s.Peek().right; s.Pop(); while (temp != null ) { s.Push(temp); temp = temp.left; } } // Function to check if // stack is empty public bool isEnd() { return s.Count!=0; } // Function to iterator to every element // using iterator public void iterate() { while (isEnd()) { Console.Write(curr().val + " " ); next(); } } } public class BinaryTree{ TreeNode root; // Driver code public static void Main(String []args) { // Let us construct a tree shown in // the above figure BinaryTree tree = new BinaryTree(); tree.root = new TreeNode(5); tree.root.left = new TreeNode(3); tree.root.right = new TreeNode(7); tree.root.left.left = new TreeNode(2); tree.root.left.right = new TreeNode(4); tree.root.right.left = new TreeNode(6); tree.root.right.right = new TreeNode(8); // Iterator to BST BSTIterator it = new BSTIterator(tree.root); // Function to test iterator it.iterate(); } } // 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.left; } } // 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 next() { let curr = q[q.length - 1].right; q.pop(); while (curr != null ) { q.push(curr); curr = curr.left; } } // 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 + " " ); next(); } } // 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 Rajput-Ji </script> |
2 3 4 5 6 7 8
Contact Us