Skip to content

Instantly share code, notes, and snippets.

@ajinkyajawale14499
Created August 3, 2019 18:34
Show Gist options
  • Save ajinkyajawale14499/1f377b224bd0bf65b9185401e7d9b3ca to your computer and use it in GitHub Desktop.
Save ajinkyajawale14499/1f377b224bd0bf65b9185401e7d9b3ca to your computer and use it in GitHub Desktop.
Preorder Traversal of Binary tree using stack
import java.util.Stack;
class Node
{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
}
}
//main class
public class Main {
//Recursive
public void preorderRecursive(Node root)
{
if(root != null){
System.out.print(root.data + " ");
preorderRecursive(root.left);
preorderRecursive(root.right);
}
}
//stack
public void inorderStack(Node root)
{
Stack<Node> s = new Stack<Node>();
while (true) {
// First print the root node and then add left node
while (root != null) {
System.out.print(root.data + " ");
s.push(root);
root = root.left;
}
// check if Stack is emtpy, if yes, exit from everywhere
if (s.isEmpty()) {
return;
}
// pop the element from the stack and go right to the tree
root = s.pop();
root = root.right;
}
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
Main obj = new Main();
obj.preorderRecursive(root);
System.out.println();
obj.inorderStack(root);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment