Binary Search Tree: Program to traverse using Preorder iterative approach

In this article, we will be going to write a program to Display the Preorder Traversal of a Binary Search Tree.
The Preorder of a Binary Search Tree: root - left subtree - right subtree

How to implement Preorder Traversal Iteratively

This traversal order can be achieved using a stack. We push root into the stack.
Then pop one element, print it and push its right child node and then left child node into stack.
Here we are pushing the right child node first and then the left child node because when we pop the element from stack
we will get the left node first. This way using stack we can retrieve the nodes in root-left-right pattern.

Algorithm

1. If root is NULL then simply return.
2. Create a stack and push the root into the stack.
3. While the stack is not empty, set the current pointer on the top node of the stack.
4. Pop one element from the stack and print it.
5. If current.right is not NULL, then push current.right into the stack.
6. If current.left is not NULL, then push current.left into the stack.

We are pushing the right subtree first because in the preorder traversal pattern is root-left-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 iterativePreorder() {
            if (Root == null) {
                return;
            }
     
            Stack nodeStack = new Stack();
            nodeStack.push(Root);
     
            while (!nodeStack.empty()) {
     
                Node current = nodeStack.peek();
                System.out.print(current.data + " ");
                nodeStack.pop();
     
                if (current.right != null) {
                    nodeStack.push(current.right);
                }
                if (current.left != null) {
                    nodeStack.push(current.left);
                }
            }
        }
     
        public static void main(String args[]) {
            BinarySearchTree tt = new BinarySearchTree();
            int[] bstElements = new int[] { 50, 20, 30, 10, 200, 70, 90 };
            int numberOfNodes = 7;
            for(int i=0;i < numberOfNodes;i++) {
                tt.insert(bstElements[i]);
            }
            System.out.println("PreOrder OF Given Binary Search Tree");
            tt.iterativePreorder();
        }
    }

Output

PreOrder OF Given Binary Search Tree
50 20 10 30 200 70 90