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



Thanks for feedback.



Read More....
Inorder Traversal - Recursive
Postorder Traversal - Iterative
Postorder Traversal - Recursive
Preorder Traversal - Iterative
Preorder Traversal - Recursive