Write a Java program to Binary Search Tree Iterator
The code demonstrates the implementation of a binary search tree iterator in Java. Let's understand how it works:
- The code starts with the import statement import java.util.Stack; , which imports the Stack class from the java.util package.
- The Binary_Search class is defined, serving as the entry point of the program.
- In the main method, a binary search tree is created by creating TreeNode objects and assigning them as the root and child nodes.
- An instance of the BSTIterator class is created, passing the root node of the binary search tree as a parameter.
- A while loop is used to iterate through the binary search tree using the iterator. The hasNext method of the iterator is called to check if there are more elements to iterate over. If hasNext returns true, the next method is called to retrieve the next element, and it is printed using the System.out.println statement.
- The TreeNode class is defined, representing a node in the binary search tree. It contains an integer value (val) and references to the left and right child nodes.
- The BSTIterator class is defined to implement the iterator for the binary search tree.
- It has a private member variable stack of type Stack<TreeNode>. This stack is used to store the nodes during iteration.
- The constructor BSTIterator takes the root node of the binary search tree as a parameter. It initializes the stack and calls the pushAll method, passing the root node to push all the left child nodes onto the stack.
- The hasNext method returns true if the stack is not empty, indicating that there are more nodes to iterate over.
- The next method pops a node from the stack, representing the current node to be returned. It then calls the pushAll method, passing the right child node of the popped node to push all the left child nodes of the right subtree onto the stack.
- The pushAll method takes a node as a parameter and pushes all the left child nodes onto the stack. It iteratively traverses the left child nodes by moving to the left child of the current node until reaching a null node.
By implementing the BSTIterator, you can iterate through a binary search tree in ascending order using a stack-based approach. It provides the ability to check if there are more elements (hasNext), retrieve the next element (next), and efficiently traverse the binary search tree in an ascending order.
Source Code
import java.util.Stack;
public class Binary_Search
{
public static void main(String[] args)
{
TreeNode root = new TreeNode(60);
root.left = new TreeNode(54);
root.right = new TreeNode(6);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(23);
BSTIterator iterator = new BSTIterator(root);
while (iterator.hasNext())
{
System.out.println(iterator.next());
}
}
}
class TreeNode
{
int val;
TreeNode left;
TreeNode right;
TreeNode(int val)
{
this.val = val;
}
}
class BSTIterator
{
private Stack<TreeNode> stack;
public BSTIterator(TreeNode root)
{
stack = new Stack<>();
pushAll(root);
}
public boolean hasNext()
{
return !stack.isEmpty();
}
public int next()
{
TreeNode node = stack.pop();
pushAll(node.right);
return node.val;
}
private void pushAll(TreeNode node)
{
while (node != null)
{
stack.push(node);
node = node.left;
}
}
}
Output
54
60
15
6
23