Skip to content

Instantly share code, notes, and snippets.

@rishabh1403
Created July 30, 2016 09:18
Show Gist options
  • Save rishabh1403/daa450ccdf238846d4cb5441c9abc15c to your computer and use it in GitHub Desktop.
Save rishabh1403/daa450ccdf238846d4cb5441c9abc15c to your computer and use it in GitHub Desktop.
Recursive and Iterative InOrder Tree Traversal
//TODO add with morristraversal
import java.util.*;
//Node class
class Node{
int data;
Node left;
Node right;
Node(int data){
this.data = data;
this.left=null;
this.right = null;
}
}
public class InOrder {
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);
iterativeInOrder(root);
System.out.println();
recursiveInOrder(root);
}
//recursive method
private static void recursiveInOrder(Node root) {
// TODO Auto-generated method stub
if(root != null){
recursiveInOrder(root.left);
System.out.print(root.data+" ");
recursiveInOrder(root.right);
}
//System.out.println();
}
//iterative method
private static void iterativeInOrder(Node root) {
// TODO Auto-generated method stub
if(root == null)
return;
Stack<Node> s1 = new Stack<Node>();
Node node = root;
while(node !=null){
s1.push(node);
node = node.left;
}
while(!s1.isEmpty()){
Node t = s1.pop();
System.out.print(t.data+" ");
if(t.right != null)
node = t.right;
while(node !=null){
s1.push(node);
node = node.left;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment