Binary Search Tree: Program to traverse using Inorder iterative approach

Write a program to display the Inorder Traversal of a Binary Search Tree using iterative approach.
The Inorder of a Binary Search Tree: left subtree - root - right subtree

How to implement Inorder Traversal Iteratively

1. This order of traversal can be achieved using a stack.
2. Push the root node into stack. Then check for its left child node and push it into stack.
3. Keep doing this until there is no more left node.
4. Then pop one node from stack and print it and the look for its right node and again keep looking for all of its left child nodes.

Algorithm

1. If root is NULL then simply return
2. Create an stack and pointer current that points to root node
3. While stack is not empty and current is not NULL
   • while current is not NULL
     • push current node into stack
     • set current as current.left
   • After current is NULL, then pop one element and print it
   • Set current as current.right

Complexity

Time Complexity : O(n) , where n is the number of nodes in binary search tree
Space Complexity : O(h), where h is the height of a binary search tree

Java Code

   import java.util.Stack;
 
    // A binary tree node
    class Node {
     
        int data;
        Node left, right;
     
        Node(int element) {
            data = element;
            left = right = null;
        }
    }
     
    Class BinarySearchTree {
     
        Node root;
     
        public void insert(int new_data) {
            Node temp, checker = null;
     
            temp = new Node(new_data);
            temp.left = temp.right = null;
            if (root == null)
                root = temp;
            else {
                checker = root;
                while (true) {
                    if (temp.data > checker.data) {
     
                        if (checker.right == null) {
                            checker.right = temp;
                            checker = temp;
                            break;
                        } else {
                            checker = checker.right;
                        }
                    } else {
                        if (checker.left == null) {
                            checker.left = temp;
                            checker = temp;
                            break;
                        } else {
                            checker = checker.left;
                        }
                    }
                }
            }
        }
     
        public void iterativeInorder() {
            if (root == null)
                return;
     
            Stack stack = new Stack();
            Node curr = root;
     
            while (curr != null || !stack.isEmpty()) {
                while (curr != null) {
                    stack.push(curr);
                    curr = curr.left;
                }
                curr = stack.pop();
                System.out.print(curr.data + " ");
                curr = curr.right;
            }
        }
     
        public static void main(String args[]) {
            BinarySearchTree bst = new  BinarySearchTree();
            int[] bstElements = new int[] { 50, 20, 30, 10, 200, 70, 90 };
            int numberOfNodes = 7;
            for (int i = 0; i < numberOfNodes; i++) {
                 bst.insert(bstElements[i]);
            }
            System.out.println("InOrder Of Given Binary Search Tree");
             bst.iterativeInorder();
        }
    } 

Output

InOrder Of Given Binary Search Tree
10 20 30 50 70 90 200