Preorder Traversal of a Binary Tree without using Recursion in Java

«
»
This is a java program to construct a binary tree and perform preorder traversal of the constructed binary tree.
Nodes visited are in the order:
visit Root node
visit Left node
visit Right node

Here is the source code of the Java Program to Perform Preorder Non-Recursive Traversal of a Given Binary Tree. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to implement non recursive pre-order traversal of Binary Search Tree
  2. import java.util.Scanner;
  3. import java.util.Stack;
  4.  
  5. class BinarySearchTreeNode
  6. {
  7.     BinarySearchTreeNode left, right;
  8.     int                  data;
  9.  
  10.     public BinarySearchTreeNode()
  11.     {
  12.         left = null;
  13.         right = null;
  14.         data = 0;
  15.     }
  16.  
  17.     public BinarySearchTreeNode(int n)
  18.     {
  19.         left = null;
  20.         right = null;
  21.         data = n;
  22.     }
  23.  
  24.     public void setLeft(BinarySearchTreeNode n)
  25.     {
  26.         left = n;
  27.     }
  28.  
  29.     public void setRight(BinarySearchTreeNode n)
  30.     {
  31.         right = n;
  32.     }
  33.  
  34.     public BinarySearchTreeNode getLeft()
  35.     {
  36.         return left;
  37.     }
  38.  
  39.     public BinarySearchTreeNode getRight()
  40.     {
  41.         return right;
  42.     }
  43.  
  44.     public void setData(int d)
  45.     {
  46.         data = d;
  47.     }
  48.  
  49.     public int getData()
  50.     {
  51.         return data;
  52.     }
  53. }
  54.  
  55. class BinarySearchTreeOperations
  56. {
  57.     private BinarySearchTreeNodes root;
  58.  
  59.     public BinarySearchTreeOperations()
  60.     {
  61.         root = null;
  62.     }
  63.  
  64.     public boolean isEmpty()
  65.     {
  66.         return root == null;
  67.     }
  68.  
  69.     public void insert(int data)
  70.     {
  71.         root = insert(root, data);
  72.     }
  73.  
  74.     private BinarySearchTreeNodes insert(BinarySearchTreeNodes node, int data)
  75.     {
  76.         if (node == null)
  77.             node = new BinarySearchTreeNodes(data);
  78.         else
  79.         {
  80.             if (data <= node.getData())
  81.                 node.left = insert(node.left, data);
  82.             else
  83.                 node.right = insert(node.right, data);
  84.         }
  85.         return node;
  86.     }
  87.  
  88.     public void preorder()
  89.     {
  90.         preorder(root);
  91.     }
  92.  
  93.     private void preorder(BinarySearchTreeNodes r)
  94.     {
  95.         Stack<BinarySearchTreeNodes> s = new Stack<BinarySearchTreeNodes>();
  96.         s.push(r);
  97.         while (!s.empty())
  98.         {
  99.             r = s.pop();
  100.             System.out.print(r.data + " ");
  101.             if (r.right != null)
  102.                 s.push(r.right);
  103.             if (r.left != null)
  104.                 s.push(r.left);
  105.         }
  106.     }
  107. }
  108.  
  109. public class Preorder_NonRecursive_BST
  110. {
  111.     public static void main(String[] args)
  112.     {
  113.         Scanner scan = new Scanner(System.in);
  114.         BinarySearchTreeOperations bst = new BinarySearchTreeOperations();
  115.         System.out.println("Enter the first 10 elements of the tree\n");
  116.         int N = 10;
  117.         for (int i = 0; i < N; i++)
  118.             bst.insert(scan.nextInt());
  119.  
  120.         System.out.print("\nPre order  : ");
  121.         bst.preorder();
  122.  
  123.         scan.close();
  124.     }
  125. }

Output:

advertisement
$ javac Preorder_NonRecursive_BST.java
$ java Preorder_NonRecursive_BST
 
Enter the first 10 elements of the tree
 
12 4 10 13 15 46 78 98 45 12
 
Pre order  : 12 4 10 12 13 15 46 45 78 98

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.